Question

Assuming binding priority (¬, ∧, ∨, →), are these sequents valid or not? If they are valid, how do you prove it? If they are not valid, what would the truth table be?

1. A → B, C → D ⊢ A ∨ C → B ∧ D
2. A ∧ ¬A ⊢ ¬(B → C) ∧ (B → C)
3. (A ∧ B) → C, C → D, B ∧ ¬D ⊢ ¬A

Answer 1

a) Given (A   B) (C  D) (A V C) (B D)

Take L.H.S (A   B) (C  D)

( ¬A V B) (¬C V D)   { Law of Implies (PQ) = ¬PVQ }

( ¬A V B) ( D V ¬C) {Commutative law (P V Q) = (Q V P)}

  ¬A V (B D) V ¬C {Associative law (P Q) R = P (Q R)}

  ¬A V ¬C V (B D)  {Commutative law (P V Q) = (Q V P)}

  ¬(A C) V (B D)   {By De Morgan's law ¬ (P Q) = ¬P V ¬Q }

  (A C) (B D) { Law of Implies ¬PVQ = (PQ) }

R.H.S

L.H.S R.H.S

So given  sequent is Not valid

Truth Table: (A   B) (C  D) (A V C) (B D)

A	B	C	D	(A  B)	(C  D)	(A V C)	(B D)	(A   B) (C D)	(A V C) (B D)
0	0	0	0	1	1	0	0	1	1
0	0	0	1	1	1	0	0	1	1
0	0	1	0	1	0	1	0	0	0
0	0	1	1	1	1	1	0	1	0
0	1	0	0	1	1	0	0	1	1
0	1	0	1	1	1	0	1	1	1
0	1	1	0	1	0	1	0	0	0
0	1	1	1	1	1	1	1	1	1
1	0	0	0	0	1	1	0	0	0
1	0	0	1	0	1	1	0	0	0
1	0	1	0	0	0	1	0	0	0
1	0	1	1	0	1	1	0	0	0
1	1	0	0	1	1	1	0	1	0
1	1	0	1	1	1	1	1	1	1
1	1	1	0	1	0	1	0	0	0
1	1	1	1	1	1	1	1	1	1

From the above truth table if we observe the last TWO columns which are not Equivalent

So given  sequent is Not valid

b) Given A ¬A ¬(B C) (B C)

Take L.H.S A ¬A

F

Take R.H.S ¬(B C) (B C)

¬(¬B V C) (¬B V C) { Law of Implies (PQ) = ¬PVQ }

[¬(¬B) ¬C ] (¬B V C)   {By De Morgan's law ¬ (P V Q) = ¬P ¬Q }

[B ¬C ] (¬B V C)  {By De Morgan's law ¬ ( ¬P) = P }

(B ¬B ) (¬C V C)  {Commutative law (P Q) = (Q P)}

(F ) (F)  { we know that A ¬A = F }

(F)  { we know that F F = F }

R.H.S

L.H.S R.H.S

A ¬A ¬(B C) (B C)

So given  sequent is Valid

c) Given [(A B) C] (C D) (B ¬D) ¬A

Take L.H.S [(A B) C] (C D) ​​​​​​​ (B ¬D)

[¬(A B) V C] (¬C V D) ​​​​​​​ (B ¬D)    { Law of Implies (PQ) = ¬PVQ }

[(¬A V ¬B) V C] (¬C V D) ​​​​​​​ (B ¬D)  {By De Morgan's law ¬ (P Q) = ¬P V ¬Q }

(¬A V ¬B) V C (¬C V D) ​​​​​​​ (¬D B)   {Commutative law (P Q) = (Q P)}

(¬A V ¬B) V (C ¬C) V (D ​​​​​​​ ¬D) B C {Associative law (P Q) R = P (Q R)}

(¬A V ¬B) V (F) V (F) B  { we know that A ¬A = F }

​​​​​​​ (¬A V ¬B) V (F V F) B  

​​​​​​​ (¬A V ¬B) V (F) B   { we know that F V F = F }

​​​​​​​ (¬A V ¬B) V B (F)   {Commutative law (P Q) = (Q P)}

​​​​​​​ ¬A V (¬B V B) (F)   {Associative law (P V Q) V R = PV (Q V R)}

​​​​​​​ ¬A V (T) (F) { we know that A V ¬A = T }

​​​​​​​​​​​​​​ ¬A V (T F)

​​​​​​​​​​​​​​ ¬A V ( F) { we know that T F = F }

​​​​​​​​​​​​​​ ¬A { we know that F ¬P = ¬P }

R.H.S

L.H.S R.H.S

[(A B) C] (C D) ​​​​​​​ (B ¬D) ¬A

So given  sequent is Valid