Propositional Logic

Overview

Propositional logic is a logical system derived from negation ($\neg$), conjunction ($\wedge$), disjunction ($\vee$), implication ($\Rightarrow$), and biconditionals ($\iff$). A proposition is a sentence that can be assigned a truth value.

Implication

Implication is denoted as $\Rightarrow$. In classical logic, it has truth table $\begin{array}{ccc}p& q& p\Rightarrow q\\ T& T& T\\ T& F& F\\ F& T& T\\ F& F& T\end{array}$

Implication has a few “equivalent” English expressions that are commonly used. Given propositions $P$ and $Q$, we have the following equivalences:

• $P$ if $Q$
• $P$ only if $Q$
• $P$ is necessary for $Q$
• $P$ is sufficient for $Q$

Bibliography

• Gries, David. The Science of Programming. Texts and Monographs in Computer Science. New York: Springer-Verlag, 1981.
• “Law of Noncontradiction,” in Wikipedia, June 14, 2024, https://en.wikipedia.org/w/index.php?title=Law_of_noncontradiction.
• • Oscar Levin, Discrete Mathematics: An Open Introduction, 3rd ed., n.d., https://discrete.openmathbooks.org/pdfs/dmoi3-tablet.pdf.
• “Principle of Explosion,” in Wikipedia, July 3, 2024, https://en.wikipedia.org/w/index.php?title=Principle_of_explosion.