502 – Propositional logic (4)

September 14, 2009

11. Completeness

 

We now want to show that whenever {S\models A,} then also {S\vdash A.} Combined with the soundness Theorem 22, this shows that the notions of provable and true coincide for propositional logic, just as they did for the tree system. The examples above should hint at how flexible and useful this result actually is. This will be even more evident for first order (predicate) logic.

Theorem 26 (Completeness) For any theory {S} and any formula {A,} if {S\models A,} then {S\vdash A.}

 

Read the rest of this entry »

Leave a Comment » | 502: Logic and set theory | Tagged: , | Permalink
Posted by andrescaicedo

502 – Propositional logic (3)

September 11, 2009

Example 13 {\lnot(A\land B)\leftrightarrow(\lnot A\lor\lnot B)} is a tautology. This is an example of De Morgan’s laws.

 

Example 14 {A\lor(B\land C)\leftrightarrow(A\lor B)\land(A\lor C)} is a tautology.

 

Definition 19 A formula {A} is satisfiable iff there is some valuation {v} such that {v\models A.} Otherwise, we say that {A} is contradictory, or unsatisfiable.

 

Remark 7 {A} is unsatisfiable iff {\lnot A} is a tautology.

 

Example 15 {(p\rightarrow q)\rightarrow(q\rightarrow p)} is not a tautology, but it is satisfiable.

 

Definition 20 If {v} is a valuation and {S} is a set of formulas, {v\models S} iff {v\models A} for all {A\in S.} For a given {S,} if there is such a valuation {v,} we say that {S} is satisfiable, or has a model, and that {v} is a model of {S.} Otherwise, {S} is unsatisfiable or contradictory.

Read the rest of this entry »

Leave a Comment » | 502: Logic and set theory | Tagged: , | Permalink
Posted by andrescaicedo

502 – Propositional logic (2)

September 10, 2009

I now proceed to present a series of results whose overall goal is to make the handling of formal proofs more efficient and natural. These results formalize different methods of reasoning commonly used in practice. A second goal in presenting these results is in preparing the way for the proof of the completeness theorem.

Theorem 7 (The deduction theorem) If {S} is a set of formulas, and {A} and {B} are formulas, then {S\cup\{A\}\vdash B} if and only if {S\vdash A\rightarrow B.}

Read the rest of this entry »

Leave a Comment » | 502: Logic and set theory | Tagged: , | Permalink
Posted by andrescaicedo

502 – Propositional logic

September 7, 2009

1. Introduction

These notes follow closely notes originally developed by Alexander Kechris for the course Math 6c at Caltech.

Somewhat informally, a proposition is a statement which is either true or false. Whichever the case, we call this its truth value.

Example 1 “There are infinitely many primes”; “{5>3}”; and “14 is a square number” are propositions. A statement like “{x} is odd,” (a “propositional function”) is not a proposition since its truth depends on the value of {x} (but it becomes one when {x} is substituted by a particular number).

 

Informally still, a propositional connective combines individual propositions into a compound one so that its truth or falsity depends only on the truth or falsity of the components. The most common connectives are:

  • Not (negation), {\lnot,}
  • And (conjunction), {\wedge,}
  • Or (disjunction), {\vee,}
  • Implies (implication), {\rightarrow,}
  • Iff (equivalence), {\leftrightarrow.}

Read the rest of this entry »

Leave a Comment » | 502: Logic and set theory | Tagged: | Permalink
Posted by andrescaicedo