Propositional Logic

Syntax and Symbols

Syntax	Terminology	Explanation	Example
`P⇒Q`	material implication	If `P`, then `Q`. Equivalent to `[~P ∨ Q]`.	`[(x=2)⇒(x²=4)]=⊤`, but not `[(x²=4)⇒(x=2)]` as `x` could also be `−2`.
`P⇔Q` `P≡Q`	material equivalence	`Q`, if and only if `P` Equivalent to `[(P⇒Q)∧(Q⇒P)]`.	`P` requires `Q` and `Q` requires `P`.
`~P`	negation	Inverts the truth value of the statement.	`~⊤ = ⊥`
`P∧Q`	logical conjunction	`P` and `Q`; True if both terms are true, false otherwise.	`⊤∧⊤=⊤`; `⊤∧⊥=⊥`
`P∨Q`	inclusive disjunction	True if either (or both) `P` or `Q` are true.	`[⊥∨⊤]=⊤`; `[⊥∨⊥]=⊥`
`P⊕Q` `P⊻Q`	exclusive disjunction	True if either (but not both) `P` or `Q` are true. Equivalent to `[(PvQ)∧~(P∧Q)]`.	`⊤⊻⊤=⊥` `⊤⊻⊥=⊤` `⊥⊻⊥=⊥`
`⊤`	tautology	Always true.
`⊥`	contradiction	Always false.
`∀x`	universal quantification	For any `x`… For each `x`…	`∀x∈ℕ` `x²>0` For each `x` in the `ℕ`atural Numbers, `x²` is greater than zero.
`∃x`	existential quantification	There exists at least one `x`.	`∃x:P(x)` There is at least one `x` such that `P(x)` is true
`∃!x`	uniqueness quantification	There exists exactly one `x`.	`∃!x:P(x)` There is exactly one `x` such that `P(x)` is true
`x≔y`	definition	`x` is defined as `y`.
`P⊢Q`	turnstile	`P` proves `Q`.	`(A→B)⊢(~B→~A)`

Rules of Replacement

Syntax	Terminology	Explanation
`P∨Q≡Q∨P` `P∧Q≡Q∧P`	commutative	Swap arguments for any `∨` or `∧`.
`P∨(Q∨R)≡(P∨Q)∨R` `P∧(Q∧R)≡(P∧Q)∧R`	associative	Parenthesis can be moved between `v` or `∧`.
`P∨⊥≡P` `P∧⊤≡P`	identity	`∨` with `⊥` becomes the non-`⊥` argument. `∧` with `⊤` becomes the non-`⊤` argument.
`P∨~P≡⊤` `P∧~P≡⊥`	negation	`∨` with two opposite values must always be `⊤`. `∧` with opposite values must always be `⊥`.
`~(~P)≡P`	double negative	`~` inverts values; `~~` inverts values back to initial value.
`P∨P≡P` `P∧P≡P`	idempotent	`∨` and `∧` operations evaporate when arguments are the same.
`P∨⊤≡⊤` `P∧⊥≡⊥`	universal bound	`∨` with `⊤` is always `⊤`. `∧` with `⊥` is always `⊥`.
`~(P∨Q)≡~P∧~Q` `~(P∧Q)≡~P∨~Q`	DeMorgan	The `~` of an `∨` is the two terms negated and `∧`ed. The `~` of an `∧` is the two terms negated and `∨`ed
`P∨(P∧Q)≡P` `P∧(P∨Q)≡P`	absorption	`∨` always requires `P`, so additional term evaporates. `∧` always requires `P`, so additional term evaporates.
`~⊥≡⊤` `~⊤≡⊥`	negation of tautology	Tautology and contradictions are known values - each is equal to the other’s negations

Set Symbols

Syntax	Terminology	Explanation	Example
`A=B`	equality	`A` has the same elements as `B`.	`{1,2,3}={1,2,3}`
`x∈A`	element of	`x` is in `A`	`A={1,2,3,4}⇒4∈A`
`x∉A`	not element of	`x` is not in `A`.	`A={1,2,3,4}⇒5∉A`
`A⊆B`	subset	`A` is a included in `B` and/or `A=B`.	`{1,3}⊆{1,2,3,4}` and `{1,3}⊆{1,3}`
`A⊊B`	proper subset	`A⊂B` and `A≠B`.	`{1,3}⊊{1,2,3,4}` but NOT `{1,3}⊊{1,3}`
`A⊄B`	not subset	`A` is not a subset of `B`.	`{1,2}⊄{1,4}`
`A∪B`	union	The result of adding `A` and `B`.	`{1,2,3}∪{3,4}={1,2,3,4}`
`A∩B`	intersection	The common elements in `A` and `B`.	`{1,2,3}∩{2,3,4}={2,3}`
`A\B` `A-B`	relative complement	The elements from `A` not in `B`.	`{1,2}\{1,3}={2}`
`A×B`	cartesian product	The combinations resulting from pairing all elements in `A` with all elements in `B`.	`{1,2}×{3,4}={(1,3),(1,4),(2,3),(2,4)}`
`{a⎮P(a)}`	set builder	A set of elements `a` with properties satisfying `P`.	`{a∈ℤ⎮a≥0}=ℕ`
`Ac` `A‘` `Ā`	complement	The elements not in `A`.	`Ac={x⎮x∉A}`
`A∆B` `A⊖B`	symmetric difference	Elements in either `A` or `B` but not both `A` and `B`.	`{1,2,3}∆{2,3,4}={1,4}`
`⎮A⎮` `#A`	cardinality	Quantity of values inside `A`.	`A={1,2,3}` `⎮A⎮=3` `#A=3`

Specifically Notated Sets

Symbol	Terminology	Explanation	Example
`∅`	null set	The empty set	`∅={}`
`𝕌`	universal set	all possible values	anything `∈𝕌`
`ℕ₁`	natural numbers	positive counting numbers	`ℕ₁={1,2,…}`
`ℕ` `ℕ₀`	natural numbers	positive counting numbers and zero	`ℕ=ℕ₀={0,1,2,…}`
`ℤ`	integers	all discrete quantities including negative	`ℤ={…,-2,-1,0,1,2,…}`
`ℚ`	rational numbers	fractions (including improper)	`ℚ={a/b⎮a,b∈ℤ,~(b=0)}`
`ℂ`	complex numbers	numbers formulated using `i`	`ℂ={a+bi⎮a,b∈ℝ,i²=-1}` `5+3i∈ℂ`
`ℝ`	real numbers	all in quantities including negative	`ℝ={x⎮-∞<x<∞}` `π∈ℝ`