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<∞} π∈ℝ |