New answers tagged

1

This isn't quick using just the standard introduction and elimination rules. But the obvious brute-force way has the following shape using a Fitch-style lay out: $((P \land Q) \to R)\\ \quad\quad |\quad \neg ((P \to R) \lor (Q \to R))\\ \quad\quad |\quad\quad|\quad (P \to R)\\ \quad\quad |\quad\quad|\quad ((P \to R) \lor (Q \to R))\\ \quad\quad ...


0

I would ask what the domain of discourse is; however, the formula $$\exists y \exists x (x \geq y)$$ is true in every nonempty domain of discourse. Let $\mathbb{U}$ be the (possibly empty) domain of discourse. Then, $a \geq a$ for all $a \in \mathbb{U}$. If $\mathbb{U}$ is nonempty, the existence of such an $a$ is guaranteed. However, if $\mathbb{U}$ is ...


-1

You can use the exportation law $ ( R \to (P \to Q)) \Leftrightarrow (( R \land P ) \to Q) $ to reduce this question to prove using natural deduction $((P \land Q) \rightarrow R) \vdash (P \rightarrow R) \lor (Q\rightarrow R)$ Which you have already asked.


0

Depending on what you know, you should prove that contrapositve is an okay step. Then, $\neg [\neg( A \to B) \to C ] \to D$ becomes $\neg D\to \neg \neg[\neg ( A \to B) \to C ]$ by contrapositive. $\neg D\to \neg \neg[\neg ( A \to B) \to C ]$ , $\neg D$ becomes $\neg \neg[\neg ( A \to B) \to C ]$ by modus ponens. $\neg \neg[\neg ( A \to B) ...


0

I believe you are going wrong with words. From Rosen's Discrete Mathematics, $p \rightarrow q$, can be expressed this way: $p$ only if $q$. $q$ if $p$. It means that if your first statement is $p \rightarrow q$, your second statement is actually $\neg q\rightarrow \neg p$ (contrapositive), not $\neg p\rightarrow \neg q$ (inverse).


0

Let $n$ a positive integer, $p$ "$n$ is a prime.", and $q$ "$n$ has no divisors other than one and itself." then first sentence can be written as $$p \rightarrow q,$$ and second sentence can be written as $$\neg q\rightarrow \neg p.$$ They are equivalent, because $\neg q\rightarrow \neg p$ is a contrapositive of $p \rightarrow q$, not an inverse. If you want ...


1

The statement you gave is equivalently "If a positive integer is prime, then it has no divisors other than one and itself." The converse is "If a positive integer is composite, then it has a divisor which is neither itself nor one." However, in definitions, we often sloppily say "if" when we mean "if and only if". For example, you might see "a metric ...


0

"A positive integer is a prime if and only if it has no divisors other than one and itself." "A positive integer is not prime if and only if it has divisors other than one and itself." These are equivalent in logic.


1

You can only find proofs for any given valid formula, if your calculus is complete. Under the precondition that your calculus is complete, it is possible to create an algorithm that will terminate for every valid formula. However, if your language is undecidable (e.g. first-order logic), you cannot find an algorithm that will terminate for every (valid and ...


0

As in your previous post, line 2) states that the following lines 2.1-2,2 are a sub-proof of: $\lnot p \vdash \lnot p \land \lnot \lnot p$. The sub-proof is: 2.1) $\lnot p$ --- assumed 2.2) $\lnot p \land \lnot \lnot p$ --- from 1) and 2.1) by $\land$-introduction. Now, we have a contradiction (often symbolized with: $\bot$) that has been derived ...


1

I don't claim to know how to do this. Here is my attempt for the second one If $\psi$ and $\varphi$ are tautologies, then $\psi\to \varphi$. Proof: Assume $\psi,\varphi$ are tautologies, and suppose that $\psi\to\varphi$ is not a tautology. Then it is possible to have $\psi$ be true and $\varphi$ false. But this is a contradiction, since $\varphi$ is a ...


1

In general, $p\to q$ does not imply the converse, $q\to p$. For example, using a truth table, you can show that $p\to q$ is logically equivalent to the contrapositive: $$p\to q \equiv \neg q \to \neg p$$ In other words, you do not need $q\to p$. If you have that $p \leftrightarrow q$, then by definition you have that $$q\to p.$$ If you are tasked with ...


0

By definition, "$a \implies b$" means "not ($a$ and not $b$)". So then "(not $b$)$\implies$(not $a$)" means "not ((not $b$) and not (not $a$))". This simplifies to "not ($a$ and not $b$)", which is the same thing as "$a \implies b$". So yeah, you only need the one direction of implication. You should probably think about this definition of $a \implies b$ if ...


3

Here is a full answer using Git Gud's approach, which is just sound advice: if you need to prove an equality or equivalence, then start at the most complex side and treat it as a simplification problem.$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}} \newcommand{\hints}[1]{\mbox{#1} \\ \quad & ...


1

The notation is a little bit "weird", but the meaning of: 2) $p \vdash q$ is to states that what follows: 2.1)-2.3), is a sub-proof aimed at deriving $q$ under the assumption $p$. Thus, having derived $q$ (in 2.3) under assumption $p$ (in 2.1), we can apply the $\to$-intro rule to derive : 3) $p \to q$ "discharging" the assumption $p$. You ...


0

Preliminary comments Yes, $\tau$ and $\tau'$ are truth assignments; see page 2: $τ : Prop → \{ 0, 1 \}$ and see Lecture 3, page 1: Definition 1. A truth assignment, $τ$ , is an element of $2^{PROP}$. See also page 4: We can now think of a formula as a circuit, which maps truth assignments to Boolean values: $\varphi : 2^{PROP} → \{ 0, 1 \}$. ...


1

We have the following, $$ \begin{align} x \lor ( y \to z ) & \equiv x\lor(\lnot y\lor z) \\ & \equiv (x\lor \lnot y)\lor z \\ & \equiv \big({\mathtt{T}}\land(x\lor \lnot y)\big)\lor z \\ & \equiv \big((\lnot x\lor x)\land(x\lor \lnot y)\big)\lor z \\ & \equiv \big(x\lor (\lnot x\land \lnot y)\big)\lor z \\ & \equiv \big((\lnot ...


0

The negation would formally be "Today is february the first and tomorrow is not Ground Hog's Day". The reason is that an implication $\phi\rightarrow\psi$ is the same as $\neg\phi\lor\psi$, then negating this using DeMorgan laws you get $\neg(\neg\phi\lor\psi) \equiv \neg\neg\phi\land\neg\psi \equiv \phi\land\neg\psi $ You could also reasoning that the only ...


0

Let$$p: \text{today is February 1}$$ $$q: \text{tomorrow is Ground Hog's Day}$$ Then your statement is, $$p\rightarrow q$$ Informally the negation of "If p then q" is p and not q, i.e. $\color{green}{\text{today is February 1}}$ and $\color{red}{\text{tomorrow is not Ground Hog's Day}}$. More formally $$p\rightarrow q \text{ is equivalent to } (\lnot ...


2

It's true, and it's legal — respectively. There's no need to be uneasy about the base case: $$\overline{v}(\phi) = v(\phi) = w(\phi) = \overline{w}(\phi).$$ However, in the chain of identities for the induction step, there is one concern, though actually it's not the one you ask about. If $\phi = \phi_1\land\phi_2$, then of course $\overline{v}(\phi) = ...


0

There's a small mistake there, “If you did all assignments but did not get an A in Discrete Math, then you either did not do all problems in the book or did not attend all lectures” translates to “$\rm (C\land \lnot D)\Rightarrow(\lnot A\lor\lnot B)$” rather than “$\rm (A\land \lnot D)\Rightarrow(\lnot C\lor\lnot B)$”, but this wont have any consequence on ...


1

For reference, the relevant passage is on page 8, section I.3. This passage is about propositional calculus (as opposed to predicate calculus). The term "variable letter" is a termporary notion, used only in this section, to explain the notion of a propostional function. You can think of a "variable letter" as a thing whose value can be $0$ or $1$. Perhaps ...


1

A Boolean function is defined to be a function $f:\{0,1\}^n\to\{0,1\}$, so both the input and the output needs to be true/false values. Functions $f:X\to\{0,1\}$ are known as indicator functions. It's called this because the set $f^{-1}(1)=A$. Then $f(x)$ takes on the value $1$ exactly when $x\in A$, so it indicates membership in the set $A$. This is often ...


1

I'm surprised nobody has given this response yet. It is my current favorite. (paraphrased from: http://mathforum.org/library/drmath/view/55617.html) I'd say "implies" means the same as "subset" in set theory. That is, when you say If it rains, then the ground gets wet you mean The set of times when it rains is a subset of ...


1

$\rm a)$ A quick check using W|A shows that your truth table is indeed correct. $\rm b)$ The question asks you to formulate certain proposition only in terms of certain connectives which are $\lnot$ and $\lor$. Obviously, the way one should attack this problem is to recall a theorem which links for instance $p\land q$ to $p\lor q$. You may recall that ...


2

According to the grouping of terms, the negation operator acts on the entirety of the implication $$\mathop{\mathrm{marriedTo}}(X,Y) \rightarrow \mathop{\mathrm{marriedTo}}(Y,X).$$ The above formula can be translated as: If X is married to Y, then Y is married to X. Therefore, the negation of that formula, $$\neg(\mathop{\mathrm{marriedTo}}(X,Y) ...


1

I don't think that it would be necessary to simplify everything, in its current form one can derive the truth table of $\small\tt P$ without too much work, $$\begin{array}{|c|c|c|c|c|c|c|c|}\hline \small\color{green}{p} &\small \color{green}{q} &\small \color{green}{r} &\small \lnot p &\small (q\oplus\lnot p) &\small \lnot(q\oplus\lnot p) ...


1

You are done, the end result is a disjunction of three terms, one of which is a conjunction and the other two are literals. – vadim123


2

So we are supposed to make the truth table for the following propositional formula: $$(p\lor \lnot q )\Rightarrow(q\land r).$$ The first observation is that we'll need $2^3$ rows (we have $p,q$ and $r$). The second is that we'll have to determine also the possible truth values for $\lnot q$, then for $(p\lor\lnot q)$ then for $(q\land r)$, and then we can ...


2

You want to prove that the calculus only produces true statements. To do this, you first prove that all the axioms are true statements, and then prove that, for each rule, if the rule takes as input true statements, then it produces a true statement. Then, by induction, this implies that the calculus produces only true statements, since every statement is ...


1

The intuition is: the rules of the calculus are "designed" in order to preserve (semantic) validity (this means soundness). Thus, if you start from a true sequent, you can never derive an "untrue" one applying the rules of the calculus.


0

You missed a few steps, and those are what you are asked to show. $\boxed{\begin{array}{r|c:l c} \text{Line} & \text{Statement} & \text{Justification} & \text{Notes} \\\hline 1 & P\to Q & \textsf{Premise 1} \\ 2 & \neg R\to \neg Q &\textsf{Premise 2} \\ 3 & P & \textsf{Premise 3} \\ \hdashline 4 & Q & ...


5

By induction on the complexity of formulas $\phi$, we prove the stronger statement: If $\phi$ contains at most one occurrence of any propositional variable, then $\phi$ is neither a tautology nor a contradiction. Suppose $\phi$ contains at most one occurrence of any propositional variable. If $\phi$ is atomic, then it's just a propositional variable, ...


1

The trick to this is to be very familiar with these laws and inference rules your professor has given you. You need to be able to recognize which rule to apply on the spot and this kind of logical thinking will take lots of practice, especially because there are a lot of laws, but getting the hang of these basic logic skills is crucial to understanding more ...


1

For both problems, you need to use distributivity. Alternately, it may be easier to simply draw up a truth table and read the CNF by negating the DNF of the negation of the statement. I'll work out both forms and you can try them on the second. First method: Using $(A\wedge B)\vee C\equiv(A\vee B)\wedge(A\vee C)$ $$(P\wedge (Q\wedge\neg R))\vee(\neg ...


0

Just a little uncomfortable with step 6 of part 2 i.e. using three steps (1,4,5) to assert a contradiction - seems like too much intuition for my liking. If possible, would like to limit myself to just the { φ ∧ ¬φ } form of contradiction. Minimal intuition - an object cannot be both itself and not itself at the same time. Is the following possible instead? ...


0

Just to make it clear why your solution is correct, here it is in Fitch-style: $\def\imp{\Rightarrow}$ Solution If $P$: [(1)]   If $Q$:     $P$. [(2); copy from (1)]   $Q \imp P$. [(3); implication introduction from (2)] $P \imp ( Q \imp P )$. [implication introduction from (3)] Notes Intuitively it is obviously correct because ...


0

In general, when you don't know how to begin, for classical logic you can use law of excluded middle. The exact details depend on which particular version of natural deduction you have, but it should be easy to translate. $\def\imp{\Rightarrow}$ Solution If $P$:   If $Q$:     $P$.   $Q \imp P$. If $\neg P$:   If $P$:   ...


0

Yes, your proof is correct (modulo $P$ is added using a different rule than $Q$). In natural deduction you have structural rules called contraction, weakening, and exchange. $$ \frac{S,P,P,T \vdash Q}{S,P,T \vdash Q}\ \text{contraction} \quad \frac{S,T \vdash Q}{S, P, T \vdash Q}\ \text{weakening} \quad \frac{S,P,Q,T \vdash R}{S,Q,P,T \vdash R}\ ...


1

Depends on what you mean by logical consequence, if you mean to ask if $p\wedge \neg p\models r$ for every formula $r$, then yes, as, by the deduction theorem, we have that this is equivalent to $\models (p\wedge \neg p)\rightarrow r$, which is true: that formula is in fact a tautology (check with truth tables).


0

If the premise is false, the conclusion is always true.


2

Let $Q$ be the statement $P\land\lnot P$. We know that $Q$ is false. Then if you have $\lnot P\implies P$ then you have $\lnot P\implies (P\land \lnot P)$, which is $P\implies Q$. But we know $Q$ is false, so $P$ is false. Indeed, every proof by contradiction can be written as: $$P\implies(A\land \lnot A)$$ for some predicate $A$. In your case, you ...


0

You don't need to proceed. You need to take a step back and try again. The Absorption equivalences are: $(A \vee B) \wedge A \equiv A, \; (A \wedge B) \vee A \equiv A $ So $$(p\wedge \neg p)\vee p \equiv \boxed{?}$$


1

Try applying distributivity to $p \wedge (\neg p \vee q)$, then go from there.


0

Let's see: \begin{align} F\lor p &\equiv ¬¬(F\lor p)\tag{Double negation}\\ &\equiv \lnot(\lnot F \land \lnot p) \tag{DeMorgan's Rule}\\ &\equiv \lnot (T \land \lnot p) \tag{$\lnot F \equiv T$}\\ &\equiv \lnot (\lnot p) \tag{Tautology }\\ &\equiv p \tag{Double negation} \end{align}


0

Okay so this is what I did, please correct me if I am wrong (p ∧ q) ⇒ r ≡ p ⇒ (q ⇒ r ) ¬(p ∧ q) v r - implication ¬p∨¬q∨r - de morgan p→(¬q∨r)- implication p→(q→r) - implication


1

It's inadequate because the operations you provide is modulo2 addition and ones complementation (ie $-1-x$). This means that any expression in $p$ and $q$ would need to be a affine combination of $p$ and $q$ with integer coefficients. That is that it should be able to write as $\alpha p + \beta q + \gamma$. Now making this odd only when $p$ and $q$ are ...


0

$\forall x\exists y(xy>0\to y>0)$ is true. (by contradiction) Let's prove that the negation of 1. is impossible. Negating 1. gives $$ \exists x \forall y (xy>0 \land y\le 0).\tag{not-1} $$ Suppose $x$ is such that (not-1) holds. Then $\forall y (xy>0 \land y\le 0)$, so $\forall y (y\le 0)$ — that is, every $y$ is less than $0$, which is ...


1

You can use some basic identities to transform the lefthand side. $$ \begin{align} (p \wedge q) \to r &\equiv p \to (q \to r) \\ \neg(p \wedge q) \vee r &\equiv \\ \neg p \vee \neg q \vee r &\equiv \\ p \to (\neg q \vee r) &\equiv \\ p \to (q \to r) &\equiv \\ \end{align} $$ I'll leave it to you to figure out which rules I'm ...


0

For the first proposition, showing that it doesn't work for $y = 0$ isn't a counterexample that disproves the statement. The qualifiers at the start of the statement, $\forall{x} \exists{y} $, mean that for every $x$, there exists at least one $y$ such that $xy \gt 0 \implies y \gt 0$. A counterexample that properly disproves the proposition would be some ...



Top 50 recent answers are included