8. In order to show that an implication p q, where p and q Are compound statemen

Question

8. In order to show that an implication p q, where p and q Are compound statements, is a tautology without going through the lengthy process of con- structing a truth table, one could proceed as follows:If p q were a tau- tology, then it would be impossible to choose truth values for the atomic constituents in such a way that the antecedent p is true but the consequent q is false. Thus at the outset one assigns p the value T and q the value F. Now one works inward in a nested fashion. Set the truth values in the next logical plane (of statement nesting) to values that are consistent with the previous currently set values in the nesting level. Thus, for example, if the current nesting plane were F and that statement decomposes into Si V S2 then botih S1 and must both be set to F. Of course, thus assignment does not have to be unique. Ultimately all atomic components will receive truth values. If then all such assignments are such that at least one atomic statement has two different truth-value assignments then, for that assignment at least, the statement is a tautology. If such an assignment is possible then it is not a tautology. Write an algorithm in C or Java pseudocode that implements this decision process

Explanation / Answer

Tautology:
Def:-
A boolean expression that will always be evaluated to be true is called a tautology.

Use:
1.Complicated boolean expressions can be simplified using tautologies.

Implication:

When we say an expression is a tautology, then it means it gives true output on all the combinations of the input.

Explanation:
=>As discussed in the question, if pVq is said to be a tautology, then all both p and q must be true and any one of p or q must be true.
=>If both p and q are false, then output results to be false.

This implies that the boolean expression PVQ is not a tautology.

We can write a pseudocode in Java to prove this without constructing truthtable.

Pseudocode:
Eg to check if (p | q)& !(p&q) is a tautology by simplifying it.

Step1: Declare the variables p,q,r,A
Step2: Open for loop and declare to 0 and define and check for less than or equal to 1, the for loop counter i
Step3:Check if the value of P equals i equals 0 is true or false
Step 4: Open another for loop and declare to 0 and define and check for less than or equal to 1,the for loop counter j
Step5:Check if the value of Q equals j equals 0 is true or false
Step6: Open another for loop and declare to 0 and define and check for less than or equal to 1, the for loop counter k
Step7: Equate A to ((p|q)& !(p&q) and equate it to p ^ q
Step 8: Print that is equation is tautology or not, depending on the boolean result from previous step.

Conclusion:

If for atleast one value of the output is F, then tautology doesnt exists.

Related Questions

Navigate

• Browse (All)
• Browse 8
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.