Logika proposisional

Kalkulus proposisional adalah sistem formal untuk menyatakan rumus proposisi dan membuktikannya dengan cara menggabungkan rumus atomik dan operator logika.

Beberapa contoh operator logika adalah:

¬ {\displaystyle \lnot } $\lnot$ (negasi)
∧ {\displaystyle \land } $\land$ (konjungsi)
∨ {\displaystyle \lor } $\lor$ (disjungsi)
→ {\displaystyle \rightarrow } $\rightarrow$ (implikasi)
↔ {\displaystyle \leftrightarrow } $\leftrightarrow$ (ekuivalensi)

Bentuk-bentuk argumen
Nama	Sequent
Modus Ponens	( ( p → q ) ∧ p ) ⊢ q {\displaystyle ((p\to q)\land p)\vdash q} $((p\to q)\land p)\vdash q$
Modus Tollens	( ( p → q ) ∧ ¬ q ) ⊢ ¬ p {\displaystyle ((p\to q)\land \neg q)\vdash \neg p} $((p\to q)\land \neg q)\vdash \neg p$
Silogisme Hipotesis	( ( p → q ) ∧ ( q → r ) ) ⊢ ( p → r ) {\displaystyle ((p\to q)\land (q\to r))\vdash (p\to r)} $((p\to q)\land (q\to r))\vdash (p\to r)$
Silogisme Disjungtif	( ( p ∨ q ) ∧ ¬ p ) ⊢ q {\displaystyle ((p\lor q)\land \neg p)\vdash q} $((p\lor q)\land \neg p)\vdash q$
Dilema Konstruktif	( ( p → q ) ∧ ( r → s ) ∧ ( p ∨ r ) ) ⊢ ( q ∨ s ) {\displaystyle ((p\to q)\land (r\to s)\land (p\lor r))\vdash (q\lor s)} $((p\to q)\land (r\to s)\land (p\lor r))\vdash (q\lor s)$
Dilema Destruktif	( ( p → q ) ∧ ( r → s ) ∧ ( ¬ q ∨ ¬ s ) ) ⊢ ( ¬ p ∨ ¬ r ) {\displaystyle ((p\to q)\land (r\to s)\land (\neg q\lor \neg s))\vdash (\neg p\lor \neg r)} $((p\to q)\land (r\to s)\land (\neg q\lor \neg s))\vdash (\neg p\lor \neg r)$
Dilema Bidireksi	( ( p → q ) ∧ ( r → s ) ∧ ( p ∨ ¬ s ) ) ⊢ ( q ∨ ¬ r ) {\displaystyle ((p\to q)\land (r\to s)\land (p\lor \neg s))\vdash (q\lor \neg r)} $((p\to q)\land (r\to s)\land (p\lor \neg s))\vdash (q\lor \neg r)$
Simplifikasi	( p ∧ q ) ⊢ p {\displaystyle (p\land q)\vdash p} $(p\land q)\vdash p$
Konjungsi	p , q ⊢ ( p ∧ q ) {\displaystyle p,q\vdash (p\land q)} $p,q\vdash (p\land q)$
Penambahan	p ⊢ ( p ∨ q ) {\displaystyle p\vdash (p\lor q)} $p\vdash (p\lor q)$
Komposisi	( ( p → q ) ∧ ( p → r ) ) ⊢ ( p → ( q ∧ r ) ) {\displaystyle ((p\to q)\land (p\to r))\vdash (p\to (q\land r))} $((p\to q)\land (p\to r))\vdash (p\to (q\land r))$
Teorema De Morgan	¬ ( p ∧ q ) ⊢ ( ¬ p ∨ ¬ q ) {\displaystyle \neg (p\land q)\vdash (\neg p\lor \neg q)} $\neg (p\land q)\vdash (\neg p\lor \neg q)$
Komutasi	( p ∨ q ) ⊢ ( q ∨ p ) {\displaystyle (p\lor q)\vdash (q\lor p)} $(p\lor q)\vdash (q\lor p)$
Asosiasi	( p ∨ ( q ∨ r ) ) ⊢ ( ( p ∨ q ) ∨ r ) {\displaystyle (p\lor (q\lor r))\vdash ((p\lor q)\lor r)} $(p\lor (q\lor r))\vdash ((p\lor q)\lor r)$
Distribusi	( p ∧ ( q ∨ r ) ) ⊢ ( ( p ∧ q ) ∨ ( p ∧ r ) ) {\displaystyle (p\land (q\lor r))\vdash ((p\land q)\lor (p\land r))} $(p\land (q\lor r))\vdash ((p\land q)\lor (p\land r))$
Dobel Negasi	p ⊢ ¬ ¬ p {\displaystyle p\vdash \neg \neg p} $p\vdash \neg \neg p$
Transposisi	( p → q ) ⊢ ( ¬ q → ¬ p ) {\displaystyle (p\to q)\vdash (\neg q\to \neg p)} $(p\to q)\vdash (\neg q\to \neg p)$
Implikasi	( p → q ) ⊢ ( ¬ p ∨ q ) {\displaystyle (p\to q)\vdash (\neg p\lor q)} $(p\to q)\vdash (\neg p\lor q)$
Ekuivalensi	( p ↔ q ) ⊢ ( ( p → q ) ∧ ( q → p ) ) {\displaystyle (p\leftrightarrow q)\vdash ((p\to q)\land (q\to p))} $(p\leftrightarrow q)\vdash ((p\to q)\land (q\to p))$
Tautologi	p ⊢ ( p ∨ p ) {\displaystyle p\vdash (p\lor p)} $p\vdash (p\lor p)$
Tertium non datur	⊢ ( p ∨ ¬ p ) {\displaystyle \vdash (p\lor \neg p)} $\vdash (p\lor \neg p)$
Non-Kontradiksi	⊢ ¬ ( p ∧ ¬ p ) {\displaystyle \vdash \neg (p\land \neg p)} $\vdash \neg (p\land \neg p)$

Pustaka

Brown, Frank Markham (2003), Boolean Reasoning: The Logic of Boolean Equations, 1st edition, Kluwer Academic Publishers, Norwell, MA. 2nd edition, Dover Publications, Mineola, NY.
Chang, C.C., dan Keisler, H.J. (1973), Model Theory, North-Holland, Amsterdam, Netherlands.
Kohavi, Zvi (1978), Switching and Finite Automata Theory, 1st edition, McGraw–Hill, 1970. 2nd edition, McGraw–Hill, 1978.
Korfhage, Robert R. (1974), Discrete Computational Structures, Academic Press, New York, NY.
Lambek, J. dan Scott, P.J. (1986), Introduction to Higher Order Categorical Logic, Cambridge University Press, Cambridge, UK.
Mendelson, Elliot (1964), Introduction to Mathematical Logic, D. Van Nostrand Company.