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 |