| Terminology | Description | Example |
| Arity | Defines how many names|constants a predicate needs.
Unary = 1, Binary = 2, … | LeftOf(x,y) … Arity = 2
Planet(pluto) … Arity = 1 |
| Atomic Sentence | Is a predicate followed by the right number (arity) of names | Bigger(saturn,pluto)
Sentence –> Pluto is a planet
Atomic sentence –> Planet(pluto) |
| Constant | Symbols used to refer to a specific object, analogous to names, and written in lowercase. | pluto |
| Conclusion | Is a logical consequence of premises. | |
| Conjunctive Normal Form (CNF) | A sentence is in conjunctive normal form (CNF) is it is a conjunction of one or more disjunctions of one or more literals. | See UNISA Chatter – Formal Logic: Propositional Logic Proofs for a proof | an example. |
| Disjunctive Normal Form (DNF) | A sentence is in disjunctive normal form (DNF) is it is a disjunction of one or more conjunctions of one or more literals. | See UNISA Chatter – Formal Logic: Propositional Logic Proofs for a proof | an example. |
| Identity Introduction | Rule that embodies the reflexity of identity | | n = n = Intro |
| Identity Elimination | Rule that embodies indiscernibility of identicals | | 1. P(n)
| 2. n = m
| 3. P(m) = Elim 1,2 |
| Indiscernibility of identicals | Also known as substitution. | If b = c, then anything is true of b is also true of c. |
| Infix Notation | With infix notation the predicate appears between two arguments | x = y |
| Informal proofs of non-consequence | Possible situation were premises are true, but conclusion is false.
See UNISA Chatter – Formal Logic: Propositional Logic Examples for more examples. | | Nearly all soccer players are funny true
| Grumpy plays soccer true
|--
| Grumpy is funny false |
| Logical Truth | Necessity | X is logically necessary if and only if it is impossible for X to be false. | See UNISA Chatter – Formal Logic: Propositional Logic Proofs for a proof | an example. |
| Logical Equivalence | X and Y are logically equivalent if and only if it is impossible for either of them to be true and the other false. | See UNISA Chatter – Formal Logic: Propositional Logic Proofs for a proof | an example. |
| Logical Consequence | X is a logical consequence of Y1, Y2, …Yn if and only if it is impossible for Y1, Y2, … Yn to be true and X is false. | See UNISA Chatter – Formal Logic: Propositional Logic Proofs for a proof | an example. |
| Negative Normal Form (NNF) | A sentence is in negative normal form (NNF) if all occurrences of Ø apply directly to atomic sentences. | See UNISA Chatter – Formal Logic: Propositional Logic Proofs for a proof | an example. |
| Object | Anything that we can make claims about | Jupiter, Pluto, Carola |
| Prefix Notation | With prefix notation the predicate precedes the arguments | Equal(x,y) |
| Predicate | Expresses properties of an object or relations between objects | Equal, LeftOf, … |
| Proof | A step-step demonstration that a conclusion follows from some premises, using either a formal or informal style. | Informal proof
Since CTOS is an operating system and all operating systems crash, it follows that CTOS will crash.
Formal proof
| 1. Square ( a )
| 2. a = b
|--
| 3. Square ( b ) |
| Quantifiers | Also see “Symbols” below
Distribution " through Ù
Distribution $ through Ú
Null Quantification
Bound variable replacement
DeMorgan Laws |
"x(P(x) Ù Q(x)) <=> "xP(x) Ù "xQ(x)
$x(P(x) Ú Q(x)) <=> $xP(x) Ú $xQ(x)
"x(P Ú Q(x)) <=> P Ú "xQ(x)
$x(P Ù Q(x)) <=> P Ù $xQ(x)
"xQ(x) <=> "yQ(y)
$xQ(x) <=> $yQ(y)
Ø"xQ(x) <=> $yØQ(y)
Ø$xQ(x) <=> "yØQ(y)
Øx($(x) Ù "Q(x)) <=> Ø$xP(x) Ú Ø"xQ(x)
"x(P(x) ® Q(x)) <=> "x(ØP(x) Ú Q(x))
<=> "xØ(P(x) Ù ØQ(x))
Ø"x(P(x) ® Q(x)) <=> $x(P(x) Ù ØQ(x))
Ø$x(P(x) Ù Q(x)) <=> "x(P(x) ® ØQ(x)) |
| Reflexity of identity | Sentences of the form a = a are always true | |
| Reiteration | Repeat an earlier step | | 1. n = n
| …
| 2. n = n = Reit 1 |
| Soundness | Implies that a deductive argument is both valid and that all premises are true.
See UNISA Chatter – Formal Logic: Propositional Logic Examples for more examples. | Valid argument, which is not sound
| All proprietary operating systems are expensive
| CTOS is a proprietary operating system
|--
| CTOS must be an expensive operating system
… why? Because first premise is false. |
| Rules | Typical rules used as part of proofs, DNF or CNF formatting includes: - De Morgan
- Elimination (Elim)
- Distribution over Ù
- Commutativity of Ù
- Idempotence of Ù
| Ø[(ØA Ù B) Ú Ø(C Ú ØD)]
= Ø(ØA Ù B) Ù Ø[Ø(C Ú ØD)] De Morgan
= Ø(ØA Ù B) Ù (C Ú ØD) Elim ØØ
= (ØØA Ú ØB) Ù (C Ú ØD) De Morgan
= (A Ú ØB) Ù (C Ú ØD) Elim ØØ
= [(A Ú ØB) Ù C] Ú [(A Ú ØB) Ù ØD] Distribution
= [C Ù (A Ú ØB)] Ú [ØD Ù (A Ú ØB)] Commutativity
= [(C Ù A) Ú (C Ù ØB)] Ú [(ØD Ù A) Ú (ØD Ù ØB)] Distribution
= (C Ù A) Ú (C Ù ØB) Ú (ØD Ù A) Ú (ØD Ù ØB) Indempotence
--> DNF format |
| Symbols | Ø Negation … not
¹ Nonidentity … is not
Ù Conjunction … and, moreover, but
Ú Disjuntion … or
® Conditional … if, if then
« Conditional … if and only if, iff
" Quantifier … all, everything
$ Quantifier … something, at least one | Ø Planet(monkey)
Pluto ¹ Saturn
Planet(pluto) Ù Planet(saturn)
Planet(moon) Ú Planet(saturn)
All P’s are in Q … "x(P(x) ® Q(x))
Some P’s are in Q … $x(P(x) Ù Q(x))
No P’s are in Q’s … $x(P(x) ® ØQ(x))
Some P’s are not in Q’s … $x(P(x) Ù ØQ(x)) |
| Symmetry of identity | If b = c then c = b | |
| Tautology | X is a tautology if and only if every row of its truth table is true. | See UNISA Chatter – Formal Logic: Propositional Logic Proofs for a proof | an example. |
| Tautology Consequence | X is a tautological consequence of Y1, Y2, …Yn if and only if there is no row in the joint truth table in which Y1, Y2 … Yn are all true and X is false. | See UNISA Chatter – Formal Logic: Propositional Logic Proofs for a proof | an example. |
| Tautology Equivalence | X and Y are tautologically equivalent if and only if there is no row of their joint table in which one value is true and the other is false. | See UNISA Chatter – Formal Logic: Propositional Logic Proofs for a proof | an example. |
| Transitivity of identity | If a = b and b = c, then a = c | |
| Truth Value | The truth value value of a statement is true if the statement is true in the circumstances, else the truth value is false. | |
| Validity | Validity implies that there is no possibility in which premises are true and the conclusion false.
See UNISA Chatter – Formal Logic: Propositional Logic Examples for more examples. | Valid and sound argument
| LeftOf ( x, z ) ;Premise
| LeftOf ( x, y ) ;Premise
|--
| LeftOf ( y, z ) ;Conclusion |