ZADANIA

  1. Udowodnić wprost następujące schematy i nazwać je.

  1. ~(α∧~β) 2. p→q 3. p≡q 4. p 5. p→q 6. p→(q→r)

_______ r→s q≡r ~p q→r q→s

α→β ____________ _______ _____ p p∧q

(p∧r)→(q∧s) p≡r q ______ __________

r∨s r∧s

p∧~q q→r r→s∧t q→~r

________ _______ _________ r

r∨s p→r p∧q→t ________

~p

  1. Udowodnić nie wprost następujące schematy logiczne.

  1. ~p 2. p→q 3. ~(p∧q) 4. p→q 5. p→q∨r 6. p→q

______ p→~r ________ ~p→q __________ r→s

~(p∧q) p ~p∨~q ______ ~q∧~r→~p p∨r

________ q _______

~(q→r) q∨s

p∨r ________ r→s s∧t s∧t

______ ~q→~p ________ r→s _________

q∨r p∧∼s→~r _________ r∨s→~p

p∨s

  1. Udowodnić następujące schematy metodą rozgałęzioną.

  1. p→q 2. p→q 3. p→(r∨q→s) 4. p→q 5. p∧q∧r∧s→t

q→r r→s ___________ r→s __________________

_______ ________ p∧q→s∨t _________ p→{q→[r→(s→t∨n)]}

p→r p∧r→q∧s p∨r→q∨s

  1. p→(r→s) 7. p→q 8. p∨q 9. p→q∨r 10. (p→q)∧(~r∨s)

_________ p→r r ___________ p∧r

p∧s→~r _______ _______ (~q∧~r)→~p _____________

p→q∧r p∧r∨q∧r (q∨t)∧∼s→~r

  1. (p∨~q)→(s∨t) 12. (p∧q∧r)∧s

r∧∼s s→t∨~t

_____________ ___________

(p∧q)→(r∨t) p∧q→r∨s∨t

ODPOWIEDZI

I. 1. 2. 3.

1. ~(α∧~β)} zał. 1. p→q} zał. 1. p≡q} zał. przechodniość

2. α } 2. r→s } 2. q≡r } równoważności

3. ~β } z.d.n. 3. p∧r } 3. p→q ROR (1)

4. ~α∨β De Morg. (1) 4. p ROK (3) 4. q→p ROR (1)

5. ~α ROA (3) (4) 5. r ROK (3) 5. q→r ROR (2)

6. sprzecz. (2) (5) 6. q RO (1) (4) 6. r→q ROR (2)

7. s RO (2) (5) 7. p→r syl. war. (3) (5)

8. q∧s RDK (6) (7) 8. r→p syl. war.

mnożenie implikacji 9. p≡r RDR (7) (8)

4. 5. 6.

1. p}zał. 1. p→q} zał. 1. p→(q→r) } zał.

2. ~p} 2. q→r } 2. q→s }

3. p∨q RDA (1) 3. p } 3. p∧q }

4. q ROA (2) (3) 4. q RO (3) (1) 4. p ROK (3)

reguła Dunsa Szkota 5. r RO (2) (4) 5. q ROK (3)

6. r∨s RDA (5) 6. s RO (2) (5)

7. q→r RO (1) (4)

8. r RO (7) (5)

9. r∧s RDK (6) (8)

7. 8. 9. 10.

  1. p→q∨r }zał. 1. p→q}zał. 1. p→(q≡r) }zał. 1. p→q } zał.

2. p∧~q } 2. q→r } 2. r→s∧t } 2. q→~r}

3. p ROK (2) 3. p } 3. p∧q } 3. r }

4. ~q ROK (2) 4. q RO (1) (3) 4. p ROK (3) 4.~q mod. toll. (2) (3)

5. q∨r RO (3) (4) 5. r RO (2) (4) 5. q ROK (3) 5. ~p mod. toll. (4) (1)

6. r ROA (5) (4) sylogizm 6. q≡r RO (1) (4)

7. r∨s RDA (6) warunkowy 7. q→r ROR (6)

8. r→q ROR (6)

9. r RO (7) (5)

10. s∧t RO (2) (9)

11. t ROK (10)

II. 1. 2. 3. 4.

1. ~p }zał. 1. p→q }zał. 1. ~(p∧q) }zał. 1. p→q }zał.

2. ~~(p∧q) } z.d.n. 2. p→~r} 2. ~(~p∨~q)}z.d.n. 2. ~p→q}

3. p∧q PN (2) 3. p } 3. ~~p NA (2) 3. ~q } z.d.n.

4. p ROK (3) 4.~~(q→r) }z.d.n. 4. ~~q NA (2) 4. ~p mod. toll. (1) (3)

5. sprzecz. (1) (4) 5. q→r PN (4) 5. p PN (3) 5. p mod. toll. (2) (3)

6. q RO (1) (3) 6. q PN (4) 6. sprzecz. (4) (5)

7. ~r RO (2) (3) 7. p∧q RDK (5) (6)

8. r RO (5) (6) 8. sprzecz . (1) (7)

  1. sprzecz. (7) (8)

5. 6. 7.

  1. p→q∨r}zał. 1. p→q} zał. 1. p→q}zał.

  2. ~q∧~r } 2. r→s } 2. p∨r }

  3. ~~p }z.d.n. 3. p∨r } 3. ~(q∨r)}z.d.n.

  4. p PN 4. ~(q∨s)}z.d.n. 4. ~q∧~r De Morg. (3)

  5. q∨r RO (1) (4) 5. ~q∧∼s De Morg.(4) 5. ~q ROK (4)

  6. ~q ROK (2) 6. ~q ROK (5) 6. ~r ROK (4)

  7. ~r ROK (2) 7. ∼s ROK(50 7. ~p mod. toll. (1) (5)

  8. r ROA (5) (6) 8. ~p mod. toll (1) (6) 8. r ROA (2) (7)

  9. sprzecz. (7) (8) 9. ~r mod. toll. (7) (2) 9. sprzecz. (6) (8)

10. r ROA (3) (8)

11. sprzecz. (9) (10)

11.

1. (p∨q)→r} zał.

8. 9. 10. 2. s∧t }

1. p→q}zał. 1. p∨q}zał. 1. (p∧q)}zał.. 3. r∨s }

2. ~q } 2. r→s} 2. s∧t } 4. ~~p } z.d.n.

3. ~~p }z.d.n. 3. p∧∼s} 3. r→s } 5. p PN (4)

4. p PN (3) 4. ~~r }z.d.n. 4 ~(p∨s)} z.d.n. 6. p∨q RDA (5)

5. ~p mod. toll. (1) (2) 5. r PN (4) 5. ~p∧∼s De Morg. (4) 7. r RO (1) (6)

6. sprzecz. (4) (5) 6. p ROK (3) 6. ~p ROK (5) 8. s ROK (2) prawo transpozycji 7. ∼s ROK (3) 7. ∼s ROK (5) 9. t ROK (2)

8 ~r mod. toll. (2) (7) 8. s ROK (2) 10. r∨s RDA (7) (8)

9. sprzecz. (4) (5) 9. t ROK (2) brak sprzeczności→reguła

10. sprzecz. (7) (8) nie jest niezawodna

III. 1. 2. 3.

1. p→q}zał. 1. p→q}zał. 1. p→(r∨q→s) }zał.

2. q→r } 2. r→s } 1.1. p∧q } zał. dod.

    1. p }zał. dod. 2.1. p∧r } zał. dod. 1.2. p ROK (2)

2.2. q RO (1) (2.1) 2.2. p ROK (2.1.) 1.3. q ROK (2)

2.3. r RO (2) (2.2.) 2.3. r ROK (2.1.) 1.4. r∨q→s RO (1) (2.1)

3. p→r (2.1.¬ 2.3.) 2.4. q RO (1) (2.2.) 1.5 r∨q RDA (2.2.)

2.5. s RO (2.3.) (2) 1.6. s RO (2.3.) (2.4.)

2.6. q∧s RDK (2.4.) (2.5.) 1.7. s∨t RDA (2.5.)

3. p∧r→q∧s (2.1.¬ 2.6.) 2. p∧q→s∨t (1.1. ¬ 1.7.)

4. 5.

1. p→q }zał. 1. p∧q∧r∧s→t}zał.

2. r→s } 1.1. p }zał. dod.

2.1. p∨r } zał. dod. 1.1.1. q }

2.2. ~(q∨s) } z.d.n. 1.1.1.1. r }

2.3. ~q }De Morg. ROK (2.2.) 1.1.1.1.1. s }

2.4. ∼s } 1.1.1.1.2. p∧q∧r∧s RDK (1.1.- 1.1.1.1.1.)

2.5. ~p mod. toll. (1) (2.3.) 1.1.1.1.3. t RO (1) (1.1.1.1.2.)

2.6. ~r mod. toll. (2) (2.4.) 1.1.1.1.4. t∨n RDA (1.1113.)

2.7. r ROA (2.1.) (2.5.) 1.1.1.2. s→t∨n (1.1.1.1.1.¬ 1.1.1.1.4.)

2.8. sprzecz. (2.6.) (2.7.) 1.1.2. r→(s→t∨n) (1.1.1.¬ 1.1.1.2.)

3. p∨r→~(q∨s)→ sprzecz. 1.2. q→[r→(s→t∨n)] (1.1.1.¬1.1.2.)

4. p∨r→ q∨s (3) 2. p→{q→[r→(s→t∨n)]} (1.1.¬1.2.)

6. 7. 8.

1. p→ (r→s) }zał. 1. p→q } zał. 1. p∨q} zał.

1.1. p∧∼s }zał. dod. 2. p→r } 2. r }

1.2. ~~r } z.d.n. 2.1. p } zał. dod. 2.1. p } zał. dod.

1.3. r PN (1.2.) 2.2. q RO (1) (2.1.) 2.2. p∧r RDK (2.1.) (2.)

1.4. p ROK (1.1) 2.3. r RO (2) (2.1.) 3. p→p∧r ( 2.1.¬2.2.)

1.5. ∼s ROK (1.1.) 2.4. q∧r RDK (2.2.) (2.3.) 3.1. q }zał. dod.

1.6. r→s RO (2) (2.1.) 3. p→ q∧r (2.1.¬ 2.4.) 3.2. q∧r RDK (3.1.) (2)

1.7. s RO (1.6.) (1.3.) 4. q→q∧r (3.1.¬3.2.)

1.8. sprzecz. (1.5.) (1.7.) 10. 5. p∧r ∨q∧r (3) (4) (1)

  1. p→(r∨s) (1.1.¬1.8.) 1. (p→q)∧(~r∨s)}zał.

2. p∧r } 12.

9. 2.1. (q∨t)∧∼s }zał. dod. 1. (p∧q∧r)∨s }zał.

1. p→q∨r }zał. 2.2. ~~r }z.d.n. 2. s→t∨~t }

1.1. ~q∧~r}zał. dod. 2.3. r PN (2.2.) 2.1. p∧q }zał. dod.

1.2. ~(q∨r) De Morg. (1.1.) 2.4. p ROK (2) 2.2. ~(r∨s∨t)} z.d.n.

1.3. ~p mod. toll. (1) (1.2.) 2.5. r ROK (2) 2.3. p ROK (2.1.)

2. (~q∧~r)→~p (1.1.¬1.3.) 2.6. q∨t ROK (2.1) 2.4. q ROK (2.1.)

2.7. ∼s ROK (2.1.) 2.5. ~r∧∼s∧~t De Morg (2.2.)

11. 2.8. p→q ROK (1) 2.6. ~r ROK (2.5.)

1. (p∨~q) (s∨t)} zał. 2.9. ~r∨s ROK (1) 2.7. ∼s ROK (2.5.)

2. r∧∼s } 2.10. ~r ROA (2.7.) (2.9.) 2.8. ~t ROK (2.5.)

2.1. p∧q }zał. dod. 2.11. sprzecz. (2.5.) (2.10.) (2.3.) 2.9. p∧q∧r ROA (1) (2.7)

2.2. r ROK (2) 3. (q∨t)∧∼s→r→ sprzecz. 2.10. r ROK (2.9.)

2.3. ∼s ROK (2) (2.1.¬2.11.) 2.11. sprzecz. (2.6.) (2.10.)

2.4. p ROK (2.1.) 4. (q∨t)∧∼s→~r 3. p∧q→~(r∨s∨t)→sprzecz.

2.5. q ROK (2.1.) (2.2.¬2.11.)

2.6. p∨~q RDA (2.4.) 4. p∧q→r∨s∨t

2.7. s∨t RO (1) (2.6)

2.8. t ROA (2.7.) (2.3.)

3. (p∧q)→ (r∨t)

ZADANIA

  1. Sprawdź za pomocą tabeli:

1. α→β 2. α∧β 3. (~p∨q)→(p∨q) 4. α→β 5. (p∧r)→(~q∨r)

α β β→α

_____ ____ _____

β α α≡β

  1. Oblicz wartość logiczną dla następujących formuł, przy podanych wartościach.

p=1

q=1 1. (p≡q)→[s→(p→~q∨s)] 2. (p≡q)≡[(q∨s)≡(~p∧q)] 3. [(p→q)→(∼s→q)]→(p∨~q)

s=1 4. [p∧(q∨s)]→[(~p∨s)→~q] 5. [(p∨q)→(q∨s)]→(~q→~p)

  1. Skontroluj metodą 0,1.

1. [(p→q)→(q→r)]∧[(p∨q)→(r∨s)] 2. (p∧q→r)→(s∧t→~p∨~q) 3. ~[(p∨q)∧(r∨s)]→(~p→r∧~q)

4. [(p→q∨s)→(~r∨q)]→(∼s∨p) 5. [(~p∧q)→(r∧∼s)]→[(~r∨p)∨(∼s∨q)] 6. [(p→q)∧(~r→s)]∨[(~p∧q)→s]

7. [(p→q)∧(q→r)]→(p→r) 8. [p→(q→~r)∧(s∨q→~p)]→[(p∧q)→(s∨r)] 9. [(p→q∨r)∧(~r→s)]→(∼s→q∨p)

10. [(p∧~q)∨s]∧(q∨r→p∨s) 11. [(p→q)∧(q→r)∧(r→s)∧(s→t)]→[~t→(s→~p)] 12. (~p∧~q)→~(p∧q)

  1. Oblicz wartość logiczną struktur syntaktycznych na podstawie opisu.

  1. Implikacja, której poprzednik jest alternatywą zbudowaną z negacji prawdziwej koniunkcji (pierwszy człon) i prawdziwej implikacji (drugi człon), a następnik jest prawdziwy.

  2. Koniunkcja zbudowana z członów alternatywy, której pierwszy człon jest fałszywy, a drugi jest implikacją, której pierwszy człon jest prawdziwy, a drugi fałszywy.

  3. Alternatywa, której pierwszy człon jest fałszywą implikacją, a drugi jest zbudowany z implikacji, której poprzednik jest alternatywą zbudowaną z dwóch członów fałszywych, a następnik fałszywą koniunkcją.

  4. Koniunkcja, której pierwszy człon jest równoważnością zbudowaną z jednego członu fałszywego, a drugiego prawdziwego, zaś drugi człon koniunkcji jest alternatywą zbudowaną z implikacji, której pierwszy człon jest prawdziwy, a drugi fałszywy.

  5. Alternatywa, której pierwszy człon jest fałszywą implikacją, a drugi jest koniunkcją zbudowaną z negacji prawdziwej implikacji i alternatywy, której oba człony są fałszywe.

  6. Implikacja, której poprzednik jest fałszywy, a następnik jest transpozycją owej implikacji.

  7. Negacja koniunkcji zbudowanej z członów fałszywej alternatywy.

  8. Negacja implikacji, której poprzednik jest prawdziwy, a następnik jest koniunkcją, której pierwszy człon jest prawdziwy, a drugi fałszywy.

  9. Alternatywa, której pierwszy człon jest negacją transpozycji prawdziwej implikacji, a drugi jest prawdziwy.

  10. Koniunkcja zbudowana z członów fałszywej implikacji.

ODPOWIEDZI

  1. 1.

    2. α

    β

    α→β

    1

    0

    0

    1

    1

    1

    0

    0

    1

    0

    1

    1

    2.

    α

    β

    α∧β

    1

    0

    0

    1

    1

    1

    0

    1

    0

    0

    0

    0

    3.

    p

    q

    ~p

    ~p∨q

    p∨q

    (~p∨q)→(p∨q)

    1

    0

    0

    0

    1

    1

    0

    0

    1

    1

    0

    0

    1

    1

    0

    1

    1

    1

    0

    1

    1

    1

    1

    1

    4.

    α

    β

    α→β

    β→α

    α≡β

    1

    0

    0

    1

    0

    0

    1

    1

    0

    0

    1

    1

    1

    1

    1

    0

    0

    1

    1

    1

    5.

    ~q

    p

    r

    p∧r

    ~q∨r

    (p∧r)→(~q∨r)

    0

    1

    0

    0

    0

    1

    0

    0

    1

    0

    1

    1

    1

    1

    1

    1

    1

    1

    1

    0

    0

    0

    1

    1

    II. 1. (p≡q)→[s→(p→~q∨s)] 2. (p≡q)≡[(q∨s)≡(~p∧q)] 3. [(p→q)→(∼s→q)]→(p∨~q)

    100 1 11 1 1 1 0 11 100 1 011 0 010 0 10 0 1 01 1 0 1 1 110

    Odp. 1 Odp. 1 Odp. 1

    4. [p∧(q∨s)]→[(~p∨s)→~q] 5. [(p∨q)→(q∨s)]→(~q→~p)

    11 0 1 1 1 0111 1 1 0 110 1 001 0 10 0 01

    Odp. 1 Odp. 0

    III. 1. [(p→q)→(q→r)]∧[(p∨q)→(r∨s)] 2. (p∧q→r)→(s∧t→~p∨~q) 3. ~[(p∨q)∧(r∨s)]→(~p→r∨~q)

    1 1 1 0 1 0 0 0 1 1 1 0 000 111 1 1 0 111 0 010 01 1 011 0 000 0 10 0 00 01

    lub 0 lub 0

    Odp.0 Odp. 0 Odp. 0

    4. [(p→q∨s)→(~r∨q)]→(∼s∨p) [(p→q∨s)→(~r∨q)]→(∼s∨p) 5. [(~p∧q)→(r∧∼s)]→[(~r∨p)∨(∼s∨q)]

    0 1 111 1 01 11 0 01 00 0 1 011 1 10 10 0 0100 10 0 0 1 1001 0 01 00 0 01 00

    lub 10 1

    Odp. 0 dla q=1 Odp. 0 dla q=0 (sprzecz.) Odp. 1

    6. [(p→q)∧(~r→s)]∨[(~p∧q)→s]

    0 1 1 0 10 00 0 101 1 0 0

    Odp. 0

    7. [(p→q)∧(q→r)]→(p→r) 8. [p→(q→~r)∧(s∨q→~p)]→[(p∧q)→(s∨r)]

    1 1 1 1 11 0 0 1 0 0 1 1 1 10 1 011 1 01 0 111 0 000

    0 0

    (sprzecz.) Odp. 1 (sprzecz.) Odp. 1

    9. [(p→q∨r)∧(~r→s)]→(∼s→q∨p)

    0 1 011 1 011 0 0 10 0 000

    Odp. 0

    10. [(p∧~q)∨s]∧(q∨r→p∨s) [(p∧~q)∨s]∧(q∨r→p∨s) 11. [(p→q)∧(q→r)∧(r→s)∧(s→t)]→[~t→(s→~p)]

    0 001 00 0 111 0 000 00 10 00 0 011 0 000 11 1 1 1 11 1 1 1 1 1 1 1 0 0 10 0 1 0 01

    lub 0 0

    Odp. 0 dla q=1 Odp. 0 dla q=0 (sprzecz.) Odp. 1

    12. (~p∧~q)→~(p∧q)

    10 1 10 0 0 010

    0

    (sprzecz.) Odp. 1

    IV. 1. Przykład rozwiązania:

    [(~p∧q)∨(r→s)]→z

    0 1 1 1 1 1

    Odp. 1

    2. 0 3. 1 4. 0 5. 0 6. 1 7. 1 8. 0 9. 1 10. 0