curs bazale matematicii

7/30/2019 Curs Bazale matematicii

1/6

Propositional logic, MFCS -2010, Mihaiela Lupea &, {UE4. Formal (axiomatic) system of propositional logicP = (Zp, Fp, Ap,Rp) where:. I" =Var _propos uCu{(,)} _ vocabulary

- var -propos = {pr,p2,...} - aset of propositional variables- c = {- (negation), n (conjunction), v (crisjunction),-+ (imprication),+> (equivatece)} ;t Fp: the set of well formed formulas, which is the smallest set of formulasatis$zing the ru1es:-base: pi e Fp,i =1,2,...;-induction:if u,rt e to then:

-UeFr,UnVeFr, UvVe Fr, (J_+VeFr, (JVeFo-closure: all formulas from Fp are obtained by applying the rules above in a finitenumber of times.

. Ap = {A1, A2, A3} _ the set of axioms of propositional logicA1: U -+ (V -+ U)A2: (U -+ (V -+ Z)) -+ ((U _+V) _+ (u + Z))A3: 1U -+V) -+ (-V -+ -U)These axioms are in fact axiomatic schemes, where (J,v,z can be arbitrarvformulas, generating an infinite number of axioms .

t Rp = {mp} - the set of inference(deduction) rules containing modus ponens rule.Notation: u,u -+vl-nprt , with the meaning: ,,from the facts ry and, u _+v wededuce (infer) v ',.

Remark: All the axioms obtained using the axiomatic schemes A:,A2.A3 aretautologies (valid formulas).

Y/


2/6

Propositional logic, MFCS -2010, Mihaiela Lupea

Definition 7: LetIJI,rJ2,..,IJn be formulas, called hypotheses and V be a formula.V is deductible (derivable) from Ul,...,Un and we denote this by Ul,'.,Un l- V' if thereis a sequence (f,,fr,...,f,,) of formulas such that f,,:Y andv; e{1,...,m} we have a) orb)or c).a) .fi Ap (axiom);b) f, e {U1,...,Un} (hypothesisc) ft, fizl- *p .fr, il < i and i2 < i

formula);(formula is inferred using modus ponens from two

existed formulas)The sequence (l ,.f2,...,.f,,,)is called the deduction of V from U1,U2,..,Un'

DefinitionS: A formulaU e ,Fo, such that A!U (or FU) iscalled theorem.Remark; The theorems are the formulas deductible only from the axioms and usingmodus ponens as inference rule.

Decision problems in propositional logic:. "Is a given propositional formulaU a theorem or not?". "Is a siven formula V deductible from the set of formulas Ul,U2,..,lJn?"Example 5: Prove that: Ll,(J -+V,V -+ Z 1- Z using the definition of deduction:We build the sequence (fl ,D,R,f4,f5) of formulas as follows:' fl uf2: U -+Vf|,f21-,,0vR:Vf4: fi -+ z

f3,f41-n,ozf5 zWe remark that fl,n,f4 are initial formulas (hypotheses), and f3, f5 are obtained usingmodus ponens. According to the above definition, we have proved that the deductionholds.

AO


3/6

Propositional logic, MFCS _2010, Mihaiela LupeaExample 6.Prove that I u -+u, building the deduction of U -+ u from the axioms only.We build the sequence of formulas (f1, D, R,f2l, f5) as follows:fI: U -+ ((U _> U) _+ U)

- from AI: u_+(V_>LD replacing V with U _+Lr ,D.: (u _> ((u _+ u) _+ u)) _+ ((u _> (u _+u)) _+ (u _+ (J))- from A2: 11u __> (v _+ z)) _+ ((u _+ v) _+ (u _> z)) using the replacements:V with U -_>u and, Zwith U;fl,f2 l*, {u _>(U _+u))_>(u _+u)f3: (u -+ (U _+ U)) _> (U _>U)f4: U _+ (U _> U)- from Al u + (V _+ (J) replacing V with (JR, f4 l- *o u _>u

f5: u _+uThe sequence (fl , D, R, fll, f5) is the deduction of u -+ty from the axioms, thereforeU -+ U is a theorem.Example 7.Prove that -UlU-+z using the definition of deduction.We build (f7, f2, f3, f4, f5) as follows:fl: -r_t --- hypothesis formulafl; -U _+ (_V _+ _(I)

- from Ar: u -+ (v -+ u) repracing, with -u and v with -tt ;fl, D.l- mp _v -+ _(Jf3: -V -+ -(J.f4: (-V -+ -U) --> (U _+.tt)- from A3 (u -+ v) --> (-v -->-u;reprac ing u with -v and v with _U :f3, f4l*o u _>vf5: U -+v

The sequence (f1, D' R, f4, f5) is the deduction of u -_, v from -u andthe axioms.

IA


4/6

Propositional logic, MFCS -2010, Mihaiela Lupea

Theorem of deduction: If U1,...,(Ia-y,UrlV, then (J1,...,(J,-vlU, ->V 'Reverse of theorem of deduction: If (J1,...,(Jn-71-Ur+Vthen (/1,...,Un-t,U"lV.Applying "n" times the theorem of deduction and its reverse we obtain:

(J1,...,(Ja*y,UnlV if and onlY if(11,...,(J n-1J- U n + fi if atd onlY if(J1,...,(Ja-2lUn-t + (Un -+Q if and only ifUtl- Uz -+ (...Un-t -+ (Un -->V)...) if and only ifl- Ur -+ (Uz + (...-+ (U, -+ V)...))

Consequences of the theorem of deduction:1. l-u -+ ((U'+ v) -+v)2. l- (U -+V)'+ ((V -+ Z) -> (U + Z)) syllogism rule3. l- (u -+ (v -+ z)) -+ (v -+ (u --> z)) permutation of the premises4. l- (U -+ (v -+ z)) -> (v nu -+ z)) reunion of the premises5. l- (u " v -+ Z) -+ (u -+ (v -+ z)) separation of the premisesExample 8: We prove the consequences I and2.1. We begin with the modus ponens rule: u, U -+vl-^o t'

Applying the theorem of deduction we obtain : U | * (U -+ V) -+ V and we continue withanother application of the same theorem: lU -+ ((U -+ V)-+V) '2. Using example I we begin with the deduction: U,(-/ -+V,V -+ z l- z

Application of the theorem of deduction ::> (J -+ V ,V -+ Z | - Lr -+ ZApplication of the theorem of deduction ::> U + V | -(V --> Z) -+ (U + Z)Application of the theorem of deduction ::> l- (U -+ V) + ((V --> Z) -+ (U -+ Z))

t:lr\J


5/6

Propositional logic, MFCS _2010, Mihaiela LupeaExample 9.

Using the theorem ofl- @ -+ r) -+ ((p Ar _) q) _+ (p ) q))stepl: we apply the reverse of the theorem of deduction to obtain the deduction to begin with:if l@ --> r) -+ (p ^r __> q) _+ (p _> q)) thenp -+rl_(pnr + q)_>(p _+ q) thenp_)r,pAr-)qlp_>q thenp)r,pAr)q,pl_qStep2: We prove the deduction obtained at Stepl.

Using Definition 7 we build the sequence of formulas: (fl , D, R, f4, f5, f6):fl: p --- premise (hypothesis)f2: p -+ r --- premisef1 nltt.t/. l_mDrrfl n f3: p ^ r (conjunction ofthe conclusions)p Ar -+ q --- premisef4, f5l-rroqq

The sequence (fl' f2, g, f4, f5, f6) is the deduction of q from the premisesp_>r,pAr_)q,p.Step3: From the deduction p -+ r , p A r -) q , p l- q we apply three times the theorem of deduction.There are 3!:6 such possibilities (to move the premises to the right side of themetasymbol l_ ) and we prove 6 theorems: T1,T2,T3,T4,T5, T6.1. the order of moving the premises to the risht sicle is;P, PAr)q, p_+rif p -+ r, p Ar ) Q, pl-4 thenp)r,pAr-)ql_p_>q then

p -> r l(p r,r + q) + (p _) q) thenl* T1 = (p --> r) -+ ((p A r -+ q) -+ (p + q))___ the theorem to be proved.2. the order of moving the premises to the right side is;P, Plr, pAr-)qif p -+ r, p Ar ) Q, pl-q thenp)r,pAr-+ql_p_>q thenp Ar -) q l- (p -> r) _+ (p _+ q) then

l- T2 = (p n r -+ q) -+ ((p -> r) _+ (p _+ q yThere can be also obtained the following theorems:lT3 = (p n r + q) -> (p _+ ((p _+ r) _+ q)))l-74 = p -> ((p Ar -) q) -+ ((p _+ r) _+ q))l- Z5 = (p -+ r) -) (p + ((p r,r _+ q) _+ q))l-76 = p -+ ((p --> r) -+ ((p nr + q) ) q ))

IJ:f4:f5:

deduction and its reverse prove

t,

f6:


6/6

Propositional logic, MFCS -2010, Mihaiela LupeaThe properties of propositional logic are: compactness, soundness, completness,coherence, noncontradictory and decidabiliry.Theorem 5. (compactness 1)An infinite sef of propositional formulas has a model if and only if each of itssubsefs has a finite model.Theorem 6.

Let S:{[J1,U2,...,U.,...] b, an infinit set ofpropositionalformula.1. S zs inconsistent if and only if !,t e N*, such that {UrU2,...,(Jk} is inconsistent.2. S is consistent if and only tf

{ Ur } zs consistent undtrJt,LIz]t is consistent und{rJt,Uz,...,U rr} is consistent und

Remarks:'. An infinite set of propositional formulas is inconsistent if and only if has aninconsistent finite subset. This can be proved in a finite number of steps.. An infinite set of propositional formulas is consistent if and only if all itssubsets (an infinite number) are consistent. This can't be proved in a finitenumber of steps.

Theorem 7. (compactness 2)A propositional formula y is a logical consequence of an infinite sef ofpropositional formulas S ( S l= V ) if and only if there is a finite subsef of S;{Ut,tJz,...,U r) c S such that U1,(J2,...,(Jrl= V.

Soundness theorem (syntactic validity implies semantic validity):If l- U then l: U (A theorem is a tautology).

Co'mpletness theorem (semantic validity implies syntactic validity) :If l=U then l- u (A tautology is a theorem).Theorem of soundness and completness for propositional logic:

l- u if and only if 1:u .Consequences of this theorem are the following properties:o The propositional logic is noncontradictory: we can't have simultaneously

Il-U and U.o The propositional logic is coherenf: not every propositional formula is a theorem.. The propositional logic is decidable: we can decide if apropositional formula is atheorem or nol The truth table method is a decision method.

curs bazale matematicii

Documents