Simple Propositional Logic Sentence

I have one very simple logical sentence :

(P → (Q ∨ R)) ↔ ((P ∧ (¬ Q)) → R)

The question is :

This sentence is VALID or not?

If this sentence is valid, how to proof it? And if this sentence is not valid, in what node the sentence is not valid if we proof it using Semantic Tree method?

And here are the answers :

There are 3 methods to solve this problem : Truth-table method, Falsification method, and Semantic Tree method. The easiest method is Truth-table, but it is not efficient. The most efficient method is Falsification method, yet it is the most difficult method to learn.

________________________________________________________

Using the first and the easiest method, the Truth-table method, answered by gedebook :

Here are the truth-tables :

P	Q	R	¬ Q
T	T	T	F
T	T	F	F
T	F	T	T
T	F	F	T
F	T	T	F
F	T	F	F
F	F	T	T
F	F	F	T

^{First Table}

1 = (Q ∨ R)	2 = (P ∧ ¬ Q)
T	F
T	F
T	T
F	T
T	F
T	F
T	F
F	F

^{Second Table}

A = (P → 1)	B = (2 → R)
T	T
T	T
T	T
F	F
T	T
T	T
T	T
T	T

^{Third Table}

A ↔ B

T

T

T

T

T

T

T

T

^{Fourth Table}

The result of all interpretations are TRUE, so it can be concluded that this sentence is VALID.

________________________________________________________

Using Falsification method, answered by lynxluna :

(P → (Q ∨ R)) ↔ ((P ∧ (¬ Q)) → R)

Dibagi jadi dua statement deh biar gampang :

U = (P → (Q ∨ R))

and

V = ((P ∧ (¬ Q)) → R)

Jadi semua statement jadi U ↔ V

Using FALSIFICATION.

Those statements will be false if one of them is TRUE and the other is FALSE.

I chose the easier path. Since both of them are implication then I need one of them to FALSE. So because it’s easier to make the disjunction to be FALSE, I take the first statement (U).

If U false then V must be TRUE to make the statements all FALSE. We set U to be false by setting these propositions.

P = TRUE

Q ∨ R = FALSE

Since Q ∨ R must be FALSE then both Q and R must be FALSE. So :

Q = FALSE

R = FALSE

After that we insert the value to the second statement (V).

((P ∧ (¬ Q)) → R) becomes

((TRUE ∧ (¬ FALSE)) → FALSE)

((TRUE ∧ TRUE) → FALSE)

( TRUE → FALSE )

FALSE

Waks… There is a glitch here.

We wants V to be TRUE but we got FALSE instead.

With this method it makes the statement is VALID.

________________________________________________________

And the last method is using Semantic Tree method (answered by myself) :

First, we assume that the value of P can be both FALSE or TRUE.

Node 2 :

(P

→

(Q

∨

R))

↔

((P

∧

(¬

Q))

→

R)

F

T

T

F

F

T

In (P → (Q ∨ R)) statement, assume that P is FALSE, then we can conclude that (P → (Q ∨ R)) is TRUE even though we don’t know the validity of (Q ∨ R) because whatever the value of (Q ∨ R), it doesn’t make the implication becomes FALSE (an implication becomes FALSE only if the antecedent is TRUE and the consequent is FALSE).

While in ((P ∧ (¬ Q)) → R) statement, if we put the value of P with FALSE, we can conclude that the (P ∧ (¬ Q)) statement is FALSE, because it’s a conjunction (one value is FALSE means the whole sentence is FALSE). So, we can conclude that ((P ∧ (¬ Q)) → R) is TRUE (because it’s an implication).

Then we can conclude that the value of (P → (Q ∨ R)) ↔ ((P ∧ (¬ Q)) → R) in node 2 is TRUE.

Node 3 :

(P

→

(Q

∨

R))

↔

((P

∧

(¬

Q))

→

R)

T

T

In (P → (Q ∨ R)) statement, if we put the value of P with TRUE, we can’t conclude the validity of (P → (Q ∨ R)) because it depends on (Q ∨ R) value. If (Q ∨ R) value is TRUE, then (P → (Q ∨ R)) statement becomes TRUE, and if (Q ∨ R) value is FALSE, then (P → (Q ∨ R)) statement becomes FALSE too (an implication).

While in ((P ∧ (¬ Q)) → R) statement, if we put the value of P with TRUE, we still can’t conclude the validity of (P ∧ (¬ Q)), because it depends on the value of (¬ Q).

Then we can conclude that this node is in-conclusive.

Because this node is in-conclusive, we need to assume a new value for the next variable.

Node 4 :

(P

→

(Q

∨

R))

↔

((P

∧

(¬

Q))

→

R)

T

F

T

T

T

F

We can’t conclude the validity of (P → (Q ∨ R)) statement because we don’t know the validity of (Q ∨ R). It depends on the value of R.

And even though we know the value of (¬ Q) is TRUE, and the value of (P ∧ (¬ Q)) is TRUE, but we still can’t conclude the value of ((P ∧ (¬ Q)) → R) statement because it depends on the value of R too (an implication).

So, we can conclude that this node is also in-conclusive.

Node 5 :

(P

→

(Q

∨

R))

↔

((P

∧

(¬

Q))

→

R)

T

T

T

T

T

T

F

F

T

Assume that the value of Q is TRUE, so the value of (Q ∨ R) is absolutely TRUE too whatever the value of R (a disjunction). And because we know that the value of P is TRUE and the value of (Q ∨ R) is TRUE, we can conclude that the value of (P → (Q ∨ R)) is TRUE.

While in ((P ∧ (¬ Q)) → R) statement, assume that the value of Q is TRUE, so we can conclude that the value of (¬ Q) is FALSE, and because the value of P is TRUE, we can conclude that the value of (P ∧ (¬ Q)) is FALSE (a conjunction).

((P ∧ (¬ Q)) → R) statement is an implication and the value of (P ∧ (¬ Q)) is FALSE, so we can conclude that the value of ((P ∧ (¬ Q)) → R) is always TRUE whatever the value of R.

Then we can conclude that the value of the whole sentence (P → (Q ∨ R)) ↔ ((P ∧ (¬ Q)) → R) is TRUE in node 5.

Node 4 is in-conclusive, it makes we need to insert a new value for the next variable, which is R.

Node 6 :

(P

→

(Q

∨

R))

↔

((P

∧

(¬

Q))

→

R)

T

F

F

F

F

T

T

T

T

F

F

F

We assume that the value of P is TRUE, the value of Q is FALSE, and the value of R is FALSE. Then we can conclude that the value of (Q ∨ R) is FALSE and the value of (P → (Q ∨ R)) is FALSE.

In ((P ∧ (¬ Q)) → R) statement, we can conclude that the value of (¬ Q) is TRUE, and the value of (P ∧ (¬ Q)) is TRUE too (a conjunction). Then we can conclude that the value of ((P ∧ (¬ Q)) → R) is FALSE (an implication).

Finally we can conclude that the value of (P → (Q ∨ R)) ↔ ((P ∧ (¬ Q)) → R) is FALSE ↔ FALSE, means TRUE.

Node 7 :

(P

→

(Q

∨

R))

↔

((P

∧

(¬

Q))

→

R)

T

T

F

T

T

T

T

T

T

F

T

T

We assume that the value of P is TRUE, the value of Q is FALSE, and the value of R is TRUE.

Then we can conclude that the value of (Q ∨ R) is TRUE and the value of (P → (Q ∨ R)) is TRUE too.

And because the value of Q is FALSE, it makes the value of (¬ Q) is TRUE, the value of (P ∧ (¬ Q)) is TRUE, and the value of ((P ∧ (¬ Q)) → R) is TRUE too.

With the validities mentioned above, we can conclude that the value of (P → (Q ∨ R)) ↔ ((P ∧ (¬ Q)) → R) is TRUE.

And here is the complete Semantic Tree :

Because all the branchs of the tree are TRUE, then we can conclude that the (P → (Q ∨ R)) ↔ ((P ∧ (¬ Q)) → R) statement is VALID.

________________________________________________________

Conclusion :

(P → (Q ∨ R)) ↔ ((P ∧ (¬ Q)) → R)

is VALID.

________________________________________________________

Further reading:

• Manna, Z. and Waldinge, R., 1985, The Logical Basis for Computer Programming, Addison-Wesley Publishing Company, Inc.
• Mano, M. M., and Kime, C. R., 2000, Logic and Computer Design Fundamentals, Prentice-Hall, Inc.

________________________________________________________

NOTE:

I post this simple logical case because there’s someone thinks that the people in my community didn’t know anything about Logic. Yet there are lots of people in my community can answer this my-simple-question.