GATE CSE 1993 | Question: 18

Question

Show that proposition $C$ is a logical consequence of the formula$$A\wedge \left(A \to \left(B \vee C\right)\right) \wedge \left( B \to \neg A\right)$$using truth tables.

Comments

how can we solve this question using Rule of inference .

Answer 1

$A\wedge(A\to (B\vee C))\wedge ( B\to \neg A)$
$\equiv A \wedge (\neg A \vee B \vee C)(\neg A \vee \neg B)$
$\equiv (A\wedge \neg B) \wedge (\neg A \vee B \vee C)$
$\equiv (A\wedge \neg B \wedge C)$
$C$ is logical consequence of a formula $X$ if, $X\to C$ is true.

$\begin{align}\text{Here, }X &\equiv A\wedge (A\to (B\vee C))\wedge ( B\to \neg A)\\ &\equiv A\wedge \neg B \wedge C\end{align}$

Checking,   
$(A\wedge \neg B \wedge C)\to C$
$\equiv  \neg(A\wedge \neg B \wedge C) \vee C$
$\equiv \neg A \vee B \vee \neg C \vee C$
$\equiv 1.$

So, $C$ is logical consequence of $A\wedge (A\to (B\vee C))\wedge (B\to \neg A).$

Comments

≡(A∧¬B)∧(¬A∨B∨C)≡(A∧¬B)∧(¬A∨B∨C)
≡(A∧¬B∧C) (How to get this from above ?)

---

This is how we can get,

(A∧¬B)∧(¬A∨B∨C)

≡ (A∧¬B∧¬A) ∨ (A∧¬B∧B) ∨ (A∧¬B∧C)

≡ F ∨ F ∨ (A∧¬B∧C)

≡ (A∧¬B∧C)

Answer 2

$A$	$B$	$C$	$A\to \left(B \vee C\right)$	$B\to\neg A$	$A\wedge \left(A \to \left(B \vee C\right)\right) \wedge \left( B \to \neg A\right)$	$C$
T	T	T	T	F	F	T
T	T	F	T	F	F	T
T	F	T	T	T	T	T
T	F	F	F	T	F	T
F	T	T	T	T	F	T
F	T	F	T	T	F	T
F	F	T	T	T	F	T
F	F	F	T	T	F	T

1. Logical consequence (also entailment) is one of the most fundamental concepts in logic. It is the relationship between statements that holds true when one logically "follows from" one or more others.

Comments

@ Anu

In the last column how to write all C is true??

---

@Lakshman Patel RJIT @Anu @srestha
 

How this last column entries are all true? Is it because X = A ∧ (A → (B ∨ C)) ∧ (B → ¬A) and X → C = T.
Can someone clear this doubt please?

---

@vupadhayayx86

$C$ is a logical consequence of a formula $X$ if, $X→C$ is true.

$A$	$B$	$C$	$A\to \left(B \vee C\right)$	$B\to\neg A$	$A\wedge \left(A \to \left(B \vee C\right)\right) \wedge \left( B \to \neg A\right)$	$\bigg[A\wedge \left(A \to \left(B \vee C\right)\right) \wedge \left( B \to \neg A\right)\bigg] \rightarrow C$
T	T	T	T	F	F	T
T	T	F	T	F	F	T
T	F	T	T	T	T	T
T	F	F	F	T	F	T
F	T	T	T	T	F	T
F	T	F	T	T	F	T
F	F	T	T	T	F	T
F	F	F	T	T	F	T

 

Answer 3

Using Inference Rules,

Modus Ponens, 
1. $(A \wedge (A \rightarrow (B \vee C ))) \rightarrow (B \vee C)$

2. $(B \rightarrow \neg A) \equiv (\neg B \vee \neg A)$

Modus Tollens,
3. $((\neg B \vee \neg A) \wedge A) \rightarrow \neg B$

Disjunctive syllogism,
4. $(\neg B \wedge (B \vee C)) \rightarrow C $