Dark Mode

156 views

0 votes

A formula is **valid** if it is *true* for any values of its variables.

Conversely, a formula is **not valid**, if there exists at least one combination of values of variables for which it is *false*.

We can use either method to solve for validity.

**Case 1: Trying to prove tautology.**

$[(p \rightarrow q) \land (q \rightarrow r)] \rightarrow r’$

$=[(p’ \lor q) \land (q’ \lor r)] \rightarrow r’$

$=[(p’ \lor q) \land (q’ \lor r)]’ \lor r’$

$=(p \land q’) \lor (q \land r’) \lor r’$

Re-writing the connectives using +, *, ‘ for simplicity sake:

$=pq’ + qr’ + r’$

$=pq’ + r’$

which is NOT a tautology.

Hence, the formula is **NOT** **valid**.

**Case 2: Trying to find atleast one combination where the formula yields false.**

An implication $A \rightarrow B$ is * false*, iff $A=True$ and $B=False$

$[(p \rightarrow q) \land (q \rightarrow r)] \rightarrow r’$

Let’s assume, $RHS = False$

i.e., $r’ = False \Rightarrow r = True$

$LHS:$

$[(p \rightarrow q) \land (q \rightarrow r)]$

$=(p’ + q) (q’ + r)$

$=p’q’ + p’r + qr$

Putting the value of $r=True \text{, or } 1$

$=p’q’ + p’.1 + q.1$

$=p’q’ + p’ + q$

$=p’ + q$

$=p \rightarrow q$

which is * false*, if $p=True$ and $q=False$

Since, when $RHS$ is * false*, $LHS$ can also become