New answers tagged

2

In your case the commas are being used to separate propositions (premises) in an argument. In your example, the premises $\neg p $ and $p\vee q$ result in $q$.


2

The comma is not part of any propositional formula. The set before the symbol $\models$ has two elements, both formulas: $\neg\, p$ $p \lor q$ The statement $\{\neg\, p, p \lor q\} \vdash q$ means: $q$ follows from the two premises, in some particular deductive system. In LaTeX/MathJax, $\vdash$ is written as "\vdash". The symbol $\models$ means: $q$ is ...


1

"From what it seems to me, proofs by contradiction, only work where boolean logic applies, where a contradiction leads to something meaningful. If a contradiction doesn't lead to anything meaningful, then it can't constitute a proof can it?" This is a correct statement. If the contradiction isn't universal, then this isn't a "proof by contradiction". ...


0

I believe proof by contradiction is readily used in fuzzy logic, which is not Boolean, so really the question depends on what is meant by "drawing a line."


0

In general, if we are trying to prove $p \Rightarrow q$ , then we do not assume it is true. Rather, we assume $p$ and, for contradiction, we also assume not $q$. Then we (hopefully) arrive at a contradiction. This means that our assumption of not $q$ was false, so we showed that $q$ is true. If, as in your example, you are just trying to prove a statement ...


0

$$ (p \iff q) \qquad\qquad\equiv\\ (p \rightarrow q) \wedge (q \rightarrow p) \qquad\equiv\\ (\neg p \vee q)\wedge(\neg q \vee p) \qquad\equiv\\ ((\neg p \vee q)\wedge \neg q) \vee ((\neg p \vee q)\wedge p) \qquad\equiv\\ (\neg p \wedge \neg q) \vee (q\wedge p). $$


0

We need to assume $\neg a$ is an abbreviation for $a \to \bot$; otherwise, there is no way to introduce negations without having an assumption with a negation in it. First note that $b \to a, a \to \bot, b \vdash \bot$ by two applications of modus ponens. Then we do three applications of the deduction theorem: first we obtain $b \to a, a \to \bot \vdash ...


2

Let $L$ be a first-order language. Schema T can be viewed as a homomorphism from the Boolean algebra of sentences of $L$ (modulo logical equivalence) to the two-element Boolean algebra. More generally, let $W$ be a theory over $L$, and consider the Boolean algebra $A$ of sentences of $L$, modulo $W$-equivalence. Then the schema can be thought of as a ...


0

[Note that a common convention is that $\land$ has higher precedence over $\lor$, which lessens brackets.] The systematic way is: Convert everything into using only $\neg,\land,\lor$. Use distributivity of $\land$ over $\lor$ and De Morgan's laws to expand into disjunctive normal form. Use the law of excluded middle to simplify. Another useful law is $P ...


0

First start with turning $[(P \lor A) \land ( \neg P \lor B)] \rightarrow (A \lor B)$ Into this $\neg [(P \lor A) \land ( \neg P \lor B)] \lor (A \lor B)$ This is where you might have been going in circles: $$ \neg [(P \lor A) \land ( \neg P \lor B)] \lor (A \lor B) \\ \neg(P \lor A) \lor \neg( \neg P \lor B) \lor (A \lor B) \\ (\neg P \land \neg A) \lor ...


3

The formulation in PlanetMath is attempting to guard against the possibility of non-logical axioms (i.e., non-trivial logical relationships amongst the propositional variables). Both statements are correct if the propositional theories don't have any non-logical axioms. However, for example, if you had an axiom saying that $p \Leftrightarrow q$, for every ...


1

Converted to an answer by popular request: If you want such a notation, use $\Bbb B$; just explain the notation at the start. The notations $\Bbb Z_2$ or $\Bbb Z/2\Bbb Z$ might be regarded as referring to a set with those same two elements, but they have sort of a different flavor, referring to a field (in the abstract-algebra sense), not a Boolean algebra. ...


1

One can prove that for the union: Let $X\models \alpha$ and $Y\models\alpha$. By the completeness theorem, we have $X\vdash\alpha$ and $Y\vdash\alpha$. That means there are derivations $x_1,\dots,x_n$ and $y_1,\dots,y_n$ such that $x_n=\alpha=y_n$ and, for every $x_i$ and $y_i$ with $i\neq n$, $x_i$ and $y_i$ are either axioms or premisses or formulas ...


0

Proposition. In the Boolean domain, the following is a tautology: $$(p \vee q) \wedge (\neg p \vee r) \Rightarrow (q \vee r)$$ Proof. If $p = 1$, then the formula becomes $r \Rightarrow q \vee r$, which is clearly true. If $p = 0$, then the formula becomes $q \Rightarrow q \vee r$, which is clearly true.


0

"A unless B" is an inclusion/exclusion type statement. You start with all possible truths. Exclude those inconsistent with $A$. Then add those consistent with $B$. Start, all possible truths: $$\{A \land B,~ A\land \lnot B,~ \lnot A \land B,~ \lnot A \land \lnot B\}$$ Truths inconsistent with $A$: $$\{\lnot A \land B,~ \lnot A \land \lnot B\}$$ Truths ...


2

If you write out the truth table for your formula... p q r p → ¬(q∨r) 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 0 To get the DNF, look at every result that is True; those lines directly correspond to the following clauses in DNF: $$(\lnot p\land\lnot q\land\lnot r)\lor(\lnot p\land\lnot q\land r)\lor(\lnot ...


2

The meaning of "unless" in English is a bit ambiguous. "You won't pass the exam unless you study". Does that imply that if you study you are guaranteed to pass the exam? I would say no.


0

"$A$ unless $B$" is read by logicians as "$A$ is guaranteed to be true, unless $B$ is true," which is not a claim that $A$ is false when $B$ is true ~ just that $B$ is true when $A$ is false.   In other words "If not $B$, then $A$", or "If not $A$, then $B$". $$\neg B\to A \\ B\leftarrow \neg A \\ A\vee B$$ You are reading it as an exclusive: "$A$ is ...


1

According to your table, (P -> P) is not a tautology, because the fourth row is left blank. It doesn't make much sense to say that (P -> P) is not a tautology. According to your table also, (P -> (Q -> P)) is not a tautology. Given that (P -> P) is a tautology, (0 -> 0) = 1. So, (0 -> (0 -> 0)) = (0 -> 1) which remains indeterminate and thus (P -> (Q -> ...


3

Your first line was correct. $A$ unless $B$ means 'given that $B$ does not happen, $A$ will happen. Thus, $A$ unless $B$ means $\neg B\implies A$. But, we can put this implication into its disjunctive to get $\neg(\neg B)\vee A$, which, in turn, is equivalent to $B\vee A$. Your mistake comes in your second line when you claim that $\neg B\implies A$ is ...


1

Material implication is good for statements like, "if $x$ is rational, then $x^2$ is rational" -- which is a statement that we would like to think of as true, and which we logically render as $$ \forall x\in \mathbb R(x \in \mathbb Q \to x^2 \in \mathbb Q). $$ We want the inner statement to be true for any $x$. In particular, we want it to be true for $\sqrt ...


1

\begin{align} (p\lor q)\to(p \land q) & \equiv (p\lor q)'\lor(p \land q)\\ & \equiv (p'\land q')\lor(p \land q)\\ & \equiv (p'\lor(p \land q))\land (q'\lor(p \land q))\\ & \equiv ((p'\lor p) \land (p'\lor q))\land ((q'\lor p) \land (q'\lor q))\\ & \equiv (T \land (p'\lor q))\land ((q'\lor p) \land T)\\ & \equiv (p'\lor q)\land ...


1

$r$ implies $s$ when it is impossible for $s$ being false while $r$ is true. That is compatible with saying that $r\rightarrow s$ is a tautology because if it is so, then there is no case in which the antecedent is true and the consequent false (which is the only case that makes the arrow false). E.g.: let $r$ be $(r_1\wedge r_2)$ and let $s$ be $r_2$. We ...


3

The trick is to expand only one of the two implications materially at first: $$\begin{align*} (p\to q)\land(q \to p) &\equiv (\neg p \lor q)\land (q\to p)\\ &\equiv \underbrace{(\neg p \land q \to p)}_{\downarrow} \lor \underbrace{(q \land q\to p)}_\downarrow& & \text{distribution}\\ &\equiv \underbrace{(\neg p \land \neg q) ...


0

$[({p}\vee{q})\rightarrow({p}\wedge{q})]\iff$ $[\neg({p}\vee{q})\vee({p}\wedge{q})]\iff$ $[(\neg{p}\wedge\neg{q})\vee({p}\wedge{q})]\iff$ $[{p}\leftarrow\rightarrow{q}]$


-1

You could write equivalence as $(p \land q) \lor (\lnot p \land \lnot q)$, which gives us, using commutation and implication law, the result you desire.


0

If (a→b) is an additional axiom, then you can prove 'c' simply by substituting b with c in (a→b), and a with any axiom in (a→b), and then applying detachment to derive c.


0

You can't, in this case. Nothing constrains $w$, so it can be $False$, and then $w\land x$ is $False$ too. 1. through 3. will only imply this if they're inconsistent (can't all be made $True$ by some assignments of values to variables). But 1.-3. are consistent: $p = q = r = True$ (and $t = $ anything).


0

Not equivalent : for (1) see Difference between proving $\forall n(Q(n) \implies P(n))$ and $\forall nQ(n) \implies \forall nP(n)$ (2) Let $Q(x)$ be $x\gt 1$, and $P(x)$ be $x\lt 1$ (3) Let $Q(x)$ be $x\gt 1$, and $P(x)$ be $x\lt 1$


1

Basically, yes. Modus Ponens is the rule of inference $\{X, X\to Y\} \vdash Y$ .   Without anything pairs of the form $X$ and $X\to Y$ you have nothing on which to use the rule. Note: it is possible to infer the conclusion from those clauses; just not with only modus ponens to work with. If you assume $\lnot A$ then using modus ponens on that and ...


0

I think because you need a proof from contradiction: Suppose $\lnot A$. Then MP gives $B$ by the first clause. Then MP again gives $A$ by the second clause. But we assume $\lnot A$, so we have a contradiction. So $\lnot \lnot A$ holds, and then if we have the rule of Tertium non datur (excluded third), we have that $A$ holds, and then the third clause by ...


1

Try to use the fact conjunction distributes over disjunction, i.e.: $$(A \vee B) \wedge C = (A \wedge C) \vee (B \wedge C).$$ So try and distribute $(\neg Q \vee \neg T) \wedge P \wedge T$ over $\neg Q \vee \neg P$. Then one of the two propositions in the resulting disjunction is never true, so you can eliminate it. Then you use the distributive law once ...


1

Hint: Distribute out the $\sim Q$ from the two disjunctions that have it. Use an absorption law to finish the proof.


1

If you mean, $\Big(\big((a\wedge b)\wedge c\big)\wedge d\Big) ~=~ a\wedge b\wedge c\wedge d$ , then this is indeed true due to the associative property of logical conjunction.


0

Is this a correct way to go or is there a precise way that I did not understand (about how considering the pair of clauses to solve)? It is a correct way.   There are others and its not easy to say which is the best way.   For myself, I'd start with statement three, the "smallest" clause, and progressively shrink the others $$\begin{align} ...


0

It is a semantic statement rather than a syntactic one. Syntax is the level of propositional calculus in which $A,B, A\wedge B$ live. Semantics is at a higher level, where we assign truth values to propositions based on interpreting them in a larger universe. Your (1), $(A\wedge B) \to C$, is a proposition. It may be true or false. However $(A\wedge B) ...


1

The symbol means "therefore". In common usage, "therefore" is a stronger statement than "if/then". When we say "p therefore q", we mean both "if p then q" and "p is true". Thus we assure that q is true, which the "if/then" statement alone does not. Mathematically: $p$ therefore $q \equiv ((p\rightarrow q) and p)$


0

1) $\lnot p\to(q\to r)$ 2) $\lnot[\lnot p]\lor [q\to r]$ using implication law 3) $p\lor [q\to r]$ using double negation law 4) $p\lor [\lnot q\lor r]$ using implication law 5) $\lnot q\lor [p\lor r]$ using associative law 6) $\lnot q\to [p\lor r]$ using implication law


1

No. You use of $\vee-$elimination is wrong. The proof rule works as is we know that $A\vee B$ hold, $A\vdash C$ and $B\vdash C$, then we may conclude $C$. In this specific case you you know that $(p\to r) \vee (q\to r) $ hold, thus is you prove a sentence $C$, you need to show that $p\to r\vdash C$ and $q\to r\vdash C$. In this specific case you want to ...


1

By soundness and completeness of propositional logic we only need to prove If $\bigwedge \Phi \vdash \bigvee \Psi$ then there exist $\phi_1,...,\phi_n$ from $\Phi$ and $\psi_1,...,\psi_m$ from $\Psi$ such that $\phi_1\land...\land \phi_n\vdash \psi_1\lor...\lor \psi_m$. Proofs are always finite and therefore involve only finitely many steps. So only ...


3

If the logic you're using admits excluded middle, you could convert the hypothesis to $$ ⋀ Φ ∧ ⋀ ¬ ψ ⊢ ⊥. $$ Then Compactness would imply some finite subset $\phi₁ ∧ … ∧ φ_n ∧ ¬ ψ₁ ∧ … ∧ ¬ ψ_m$ of the left hand side entails a contradiction, and from there you can move $\psi₁$ through $\psi_m$ back to the right hand side.


0

Resolution gets used a fair amount in automated reasoning. This paper gives you an example.


2

What they are asking is how many possible relationships like this are there. You have 4 rows, first 2 columns are fixed, last column has 4 entries with T/F each, so $2^4=16$ total choices.


3

For different formulae, the third column above can have different 4-tuples of T or F. So there are $2^4$ different formulae. For example, $P\wedge Q$, $$\begin{array}{cc|c} P&Q&P\wedge Q\\\hline T&T&T\\ T&F&F\\ F&T&F\\ F&F&F \end{array}$$ is another truth table with a different 4-tuple $(T,F,F,F)$. In fact, for any ...


0

Suppose $(p \to q) \land (q \to r) \land \neg(r \to p)$ Assume $q$, then we have $(p\to \top) \wedge (\top\to r)\wedge \neg (r\to p)$, which is $r\wedge \neg p$ $$\begin{array}{l}(p\to \top) \wedge (\top\to r)\wedge \neg (r\to p)\\ \top \wedge (\top\to r)\wedge \neg(r\to p)\\ (\top\to r)\wedge \neg(r\to p)\\ r\wedge \neg (r\to p)\\ r\wedge \neg ...


0

The only possibility that $\neg (r \Rightarrow p) $ is true is that $ \neg p \land r$. For ($q \Rightarrow r$) to be true also, we can take $q$ or $\neg q$, hence $(q \lor \neg q)$. That is also the case for $(p \Rightarrow q)$, since we already have $\neg p$, so we can take $q$ or $\neg q$, hence $(q \vee \neg q)$. Since ($q \lor \neg q$) is always true, we ...


1

Your answer key seems to be writing down the desired statement to be proven before proceeding to prove it, and after that marking it with a tick when done. For example in the case of the second tick the line 2.2 is proven from lines 2.2.1 to 2.2.3. Of course, mathematically it is irrelevant to the formal proof, but in practice it is useful to be able to ...


1

In general, am I allowed to do $(p ∨ (¬p ∧ ¬q)) ∧ (q ∨ (¬p ∧ ¬q))$ Yes, we can.   That is an application of distribution.   Only we don't stop here: were not CNF yet. We can do it again on the first factor: $((p ∨ ¬p) ∧ (p ∨ ¬q)) ∧ (q ∨ (¬p ∧ ¬q))$ But wait: there's a tautology: $(p∨\neg p)$, which can be absorbed (by conjunctive ...


1

You are on the right track, just keep going: \begin{align} (p\wedge q) \vee (\neg p \wedge \neg q) =&\ \big(p \vee (\neg p \wedge \neg q)\big) \wedge \big(q \vee (\neg p \wedge \neg q\big) \\ =&\ \big((p \vee \neg p) \wedge (p \vee \neg q)\big) \wedge \big((q \vee \neg p) \wedge (q \vee \neg q)\big) \\ =&\ (p \vee \neg p) \wedge (p \vee \neg q) ...


0

Note that axiom 1 allows you to get a conditional which has any antecedent you want so long as the consequent is a theorem. For this reason, we can call axiom 1 'recursive variable prefixing.' Axiom 2 we can call 'self-distribution'. Thus, use recursive variable prefixing and self-distribution to deduce (A→A). Use recursive variable prefixing and (A→A) ...



Top 50 recent answers are included