In mathematical logic and computer science, propositional logic deals with propositions that can be either true or false.
Complex statements are built by connecting atomic propositions with logical operators:
Conjunction (AND $\land$): $P \land Q$ is true only if both $P$ and $Q$ are true.
Disjunction (OR $\lor$): $P \lor Q$ is true if at least one is true.
Negation (NOT $\neg$): $\neg P$ flips true to false and false to true.
Implication (IF...THEN $\to$): $P \to Q$ is false only when a true premise leads to a false conclusion ($\neg P \lor Q$). If the premise is false, the implication is vacuously true!
Equivalence (IFF $\leftrightarrow$): $P \leftrightarrow Q$ is true when both have the identical truth value.
The Boolean Satisfiability Problem (SAT)
One of the most famous problems in all of theoretical computer science is SAT: given a complex boolean formula, does there exist an assignment of truth values to the variables that makes the overall formula true?
Because Prolog's execution engine is based on Horn-clause logic, we can define truth tables and solve SAT problems effortlessly!
bool(true). bool(false). and(true, true, true). and(true, false, false). and(false, true, false). and(false, false, false). implies(P, Q, Res) :- % Implication: True -> False is False: Replace ???? with false
(P = true, Q = false -> Res = ???? ; Res = true). goal: and(P, Q, true).
Move the mouse over a dotted box for more information.
Tautology: A formula that is true under every possible truth assignment (e.g., $P \lor \neg P$, the Law of Excluded Middle).
Contradiction: A formula that is false under every truth assignment (e.g., $P \land \neg P$).
Contingency (Satisfiable): A formula that can be either true or false depending on the inputs.
Now you try. Run the code and verify that Result is true for all 4 truth value assignments of P and Q.
Type your code here:
See your results here:
The code has ???? for the truth value of True $ o$ False. Replace ???? with false, then click Run to generate the truth table! generated for $(P \land Q) \to (P \lor Q)$ across all 4 combinations of $P$ and $Q$!
Notice that Result = true for every single row. This proves that $(P \land Q) \to (P \lor Q)$ is a mathematical tautology!
Share your code
Show a friend, family member, or teacher what you've done!