Propositional Logic

Syntax and Symbols

SyntaxTerminologyExplanationExample
P⇒Qmaterial implicationIf 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 equivalenceQ, if and only if P
Equivalent to [(P⇒Q)∧(Q⇒P)].
P requires Q and Q requires P.
~PnegationInverts the truth value of the statement.~⊤ = ⊥
P∧Qlogical conjunctionP and Q; True if both terms are true, false otherwise.⊤∧⊤=⊤; ⊤∧⊥=⊥
P∨Qinclusive disjunctionTrue if either (or both) P or Q are true.[⊥∨⊤]=⊤; [⊥∨⊥]=⊥
P⊕Q
P⊻Q
exclusive disjunctionTrue if either (but not both) P or Q are true.
Equivalent to [(PvQ)∧~(P∧Q)].
⊤⊻⊤=⊥
⊤⊻⊥=⊤
⊥⊻⊥=⊥
tautologyAlways true.
contradictionAlways false.
∀xuniversal quantificationFor any x
For each x
∀x∈ℕ
x²>0
For each x in the atural Numbers, is greater than zero.
∃xexistential quantificationThere exists at least one x.∃x:P(x)
There is at least one x such that P(x) is true
∃!xuniqueness quantificationThere exists exactly one x.∃!x:P(x)
There is exactly one x such that P(x) is true
x≔ydefinitionx is defined as y.
P⊢QturnstileP proves Q.(A→B)⊢(~B→~A)

Rules of Replacement

SyntaxTerminologyExplanation
P∨Q≡Q∨P
P∧Q≡Q∧P
commutativeSwap arguments for any or .
P∨(Q∨R)≡(P∨Q)∨R
P∧(Q∧R)≡(P∧Q)∧R
associativeParenthesis 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)≡Pdouble 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
DeMorganThe ~ 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 tautologyTautology and contradictions are known values - each is equal to the other’s negations

Set Symbols

SyntaxTerminologyExplanationExample
A=BequalityA has the same elements as B.{1,2,3}={1,2,3}
x∈Aelement ofx is in AA={1,2,3,4}⇒4∈A
x∉Anot element ofx is not in A.A={1,2,3,4}⇒5∉A
A⊆BsubsetA is a included in B and/or A=B.{1,3}⊆{1,2,3,4} and {1,3}⊆{1,3}
A⊊Bproper subsetA⊂B and A≠B.{1,3}⊊{1,2,3,4} but NOT {1,3}⊊{1,3}
A⊄Bnot subsetA is not a subset of B.{1,2}⊄{1,4}
A∪BunionThe result of adding A and B.{1,2,3}∪{3,4}={1,2,3,4}
A∩BintersectionThe common elements in A and B.{1,2,3}∩{2,3,4}={2,3}
A\B
A-B
relative complementThe elements from A not in B.{1,2}\{1,3}={2}
A×Bcartesian productThe 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 builderA set of elements a with properties satisfying P.{a∈ℤ⎮a≥0}=ℕ
Ac
A‘
Ā
complementThe elements not in A.Ac={x⎮x∉A}
A∆B
A⊖B
symmetric differenceElements in either A or B but not both A and B.{1,2,3}∆{2,3,4}={1,4}
⎮A⎮
#A
cardinalityQuantity of values inside A.A={1,2,3}
⎮A⎮=3
#A=3

Specifically Notated Sets

SymbolTerminologyExplanationExample
null setThe empty set∅={}
𝕌universal setall possible valuesanything ∈𝕌
ℕ₁natural numberspositive counting numbersℕ₁={1,2,…}

ℕ₀
natural numberspositive counting numbers and zeroℕ=ℕ₀={0,1,2,…}
integersall discrete quantities including negativeℤ={…,-2,-1,0,1,2,…}
rational numbersfractions (including improper)ℚ={a/b⎮a,b∈ℤ,~(b=0)}
complex numbersnumbers formulated using iℂ={a+bi⎮a,b∈ℝ,i²=-1}
5+3i∈ℂ
real numbersall in quantities including negativeℝ={x⎮-∞<x<∞}
π∈ℝ