Tag Info

Hot answers tagged propositional-calculus

4

Combine the $\neg B$ with premise 3 to get $A$, which with premise 1 gives you $\neg C$, and thus the contradiction with $C$ you are looking for.

3

Because ∀x(K(Al, x) → (x = Bill)) also allows the possibilty that Al doesn't know any x.

2

Unpacking the book's reasoning a bit, when $5\mid x$ is true, then $5\mid xy$ is true can be expanded to $5\mid x$ implies $5\mid xy$, and since I did not say anything about $5\mid y$ just then, the implication is true when $5\mid y$ is true and it also is true when $5\mid y$ is false. Or to put it another way, when someone says "suppose $5\mid x$ ...

2

The case $5|x$ and $5|y$ is already covered by the other cases, so it is not necessary to consider it separately. The important thing is to make sure that the cases you consider are exhaustive.

2

From $\neg R \to P$ you can indeed infer $\neg P \to R$, thought this is typically considered Contraposition rather than Modus Tollens, which would infer $R$ from $\neg R \to P$ and $\neg P$ And no, this is not a fallacy. I think you might be thinking of the Denying the Antecedent Fallacy, which would try to infer $\neg P$ from $\neg R \to P$ and $R$ ... ...

2

It is an implication. If Al knows x, then x is Bill. But without the first part we do not actually know if Al knows Bill, just that if Al does know somebody, it must be Bill.

2

The statement $\Gamma\vDash \phi$ has the meaning "in all models where the formulas in $\Gamma$ are true, also the formula $\phi$ is true." If we want to show that $\Gamma\vDash\phi$, two methods seem reasonable: If we show that $\phi$ is a direct consequence of (some of) the formulas in $\Gamma$, then we have proved that $\Gamma\vDash\phi$. If we show ...

2

The 'correct' transformation depends on what rules you have .... Here is a transformation that uses pretty elementary equivalence principles: $$(A \wedge \neg B) \wedge (A \vee \neg C)$$ $$\overset{Commutation}{=}$$ $$(\neg B \land A) \wedge (A \vee \neg C)$$ $$\overset{Association}{=}$$ $$\neg B \land (A \wedge (A \vee \neg C))$$ $$\overset{... 2 I know from your previous question that you have shown \neg \neg p \vdash p So, since you can easily show that p, p \to \neg q \vdash \neg q, you can use the fact that \neg \neg p \vdash p to show that p, \neg \neg (p \to \neg q) \vdash \neg q. Thus, by the Deduction Theorem, you have p \vdash \neg \neg (p \to \neg q) \to \neg q. Likewise, since ... 1 If the proposition Q is true, then P \rightarrow Q is true regardless of whether P is true. In particular, K(\text{Al}, \text{Bill}) \rightarrow (\text{Bill} = \text{Bill}) is true regardless of whether Al knows Bill. You need K(\text{Al}, x) \text{ iff } (x = \text{Bill}). 1 Starting from the formula : ¬((q \lor ¬p) \land ¬r), we have to use the tautological equivalence : \lnot (\alpha \land \beta) \equiv (\alpha \to \lnot \beta) to get : (q \lor ¬p) \to r, and then use Material Implication : (p \to q) \to r. Same approach for the second one : (p \lor ¬q) \lor (p \land (q \land ¬r)). We have to replace (... 1 Minimum-sized is asking you to find a structure with the smallest possible number of elements in which the sentence is not valid. Just because the relation is given the name < doesn't mean that it has to have the usual properties of an ordering relation. Take a model with 2 elements a and b say and define x < y to hold iff x \neq y. Then a &... 1 Sure, you can 'ignore' the \lor \neg q while working on the rest. You are likewise 'ignoring' the \to s. It's ok: boolean logic laws can be applied to component statement that, as such, ignore everything else about that statement, i.e.just leave the rest alone. Yes, you can treat the p \land q as a single statement that, when distibuted over r \lor \... 1 The goal is a conditional, so do a conditional proof: assume B, and try to get to \neg C \to D Ok, but that new goal is itself a conditional, so do a second conditional proof inside the first one: assume \neg C, and try to got to D Now, given the premise, it is clear that you can get to D if only you can prove B \to \neg C. So, the new goal is ... 1 \def\fitch#1#2{\quad\begin{array}{|l}#1\\\hline#2\end{array}} Always keep your mind on the goal. You are attempting to deduce \neg C using a subproof with an assumption of C. The goal of this subproof is a contradiction. The means of achieving that goal is using the third premise and \vee-elimination.$$\fitch{~~1.~A\to\neg C\\~~2.~\neg (B\wedge\...

1

The strategy here appears to be the deliberate introduction of a contradiction by assuming $(¬S∧−J)∧S$. As far as I can tell, one could use this strategy to derive $S→Q$ where $Q$ stands for any statement. Yes. That is a typical use of the Rule of Explosion. $$\def\fitch#1#2{\quad\begin{array}{|l}#1\\\hline#2\end{array}}\fitch{\neg S}{\fitch{S}{\neg S\... 1 I'll start from the end and answer your question - no, that's not the logical consequence. I will now explain why. Your theorem concerning the relation between entailmaent is correct. Let's write it again.  T \models A \Leftrightarrow T\cup \{ \neg A\}  is not satisfiable This is logically equivalent to:  \neg ( T \models A ) \Leftrightarrow \neg ( T\... 1 Another trick: The Consensus Theorem says: XY+X'Z=XY+X'Z+YZ which can be generalized to: Nested Consensus WXY+WX'Z=WXY+WX'Z+WYZ Applying this to your statement:$$A'B'C+A'C'D'+AC'D+A'BC'\overset{Consensus: AC'D+A'BC' = AC'D+A'BC'+BC'D}{=}A'B'C+A'C'D'+AC'D+A'BC'+BC'D\overset{Consensus: A'C'D'+BC'D = A'C'D'+BC'D+A'BC'}{=}A'B'...

Only top voted, non community-wiki answers of a minimum length are eligible