Clipart Illustration of a White Character Sitting On The Ground And Using A Laptop Computer See UNISA – Summary of 2010 Posts for a list of related UNISA posts. This post is one of three summary posts I will be building up over the next couple of months, so if you are following this topic or completing the same course as I this year, you may want to bookmark this post and come back occasionally for a peek and to give “candid” feedback.

** UNDER CONSTRUCTION ** Last change: 2010-04-05

Summary

The eye of this excursion is the first-order logic (FOL) language which goes back to Aristotle and is used by a variety of environments such as mathematics, philosophy, linguistics and artificial intelligence.

image image

The two examples above are referred to in the terminology summary below:

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

Some of these expressions and proofs are a real tongue twister … but formal logic is fun … so far :)