Question

Show that (-91(pvp)) +n is a tautology (i.e. (91(pvp)) +7=T). (a) (3 points) Show the equivalence using truth tables (b) (4 points) Show the equivalence by establishing a sequence of equiv- alences. You can only use the equivalences in Table 6 and the first equivalence in Table 7. Show your work by annotating every step.

Answer 1

Answer:

The statement $(\lnot q \land(p\lor p))\rightarrow \lnot q$ is a tautology

Step-by-step explanation:

A tautology is a statement that is true for every assignment of truth values to its simple components.

a) A truth table shows how the truth or falsity of a compound statement depends on the truth or falsity of the simple statements from which it's constructed.

We have the statement $(\lnot q \land(p\lor p))\rightarrow \lnot q$, which is compound by these statements:

• $\lnot q$
• $p\lor p$
• $\lnot q \land(p\lor p)$

and we are going to use these simple statements to build the truth table.

The last column contains only true values. Therefore, the statement is a tautology.

b) We are going to use the table of logical equivalences as follows:

$(\lnot q \land(p\lor p))\rightarrow \lnot q \equiv$

$\equiv \lnot(\lnot q \land(p\lor p)) \lor \lnot q$ by the logical equivalence involving conditional statement.

$\equiv \lnot(\lnot q) \lor \lnot(p\lor p) \lor \lnot q$ by De Morgan's Law

$\equiv q \lor \lnot(p\lor p) \lor \lnot q$ by the Double negation law

$\equiv q \lor \lnot p \lor \lnot q$ by the Idempotent law

$\equiv (q \lor \lnot q)\lor \lnot p$ by Associative law

$\equiv T\lor \lnot p$ by Negation law

$\equiv T$ by Domination law