1105140237

18

ROZDZIALI. RACHUNEK ZDAŃ

Ćwiczenie 1.10 Wyraź negację, koniunkcję, alternatywę, implikację oraz równoważność za pomocą kreski Sheffera.

Ćwiczenie 1.11 Udowodnij łączność spójnika A.

Ćwiczenie 1.12 Pokaż, że

1-    M h p,

2-    {p, q] |= P A q,

{p, -■?>} h q,

4.    {p,p —> q} \= q, (reguła Modus Ponens)

5.    {a V p, —>ce V q} |= pV q (reguła rezolucji).

Ćwiczenie 1.13 Zapisz w notacji polskiej następujące formuły:

1.    {(p V q) V r) V s

2.    (pV q) —» (~>r A s)

3.    HpVę)) o (ipA-ng)

Ćwiczenie 1.14 Ile jest waluacji n : {pi,... ,Pio} —► {®, 1} takich, że 1■ Tt (= (pi V . . . V Pio),

2.    ir f= pi —>■ (p2 V ... V pio),

3.    tt 1= (Pi V ... V p₅) A (p₆ V ... V Pio) ?

Zadanie 1.1 Pokaż, że każde zdanie rachunku zdań zawiera taką samą liczbę nawiasów otwierających co zamykających.

Zadanie 1.2 Pokaż, że jeśli zdanie jest zbudowane tylko ze stałych zdaniowych (czyli nie zawiera żadnej zmiennej zdaniowej), to jest ono tautologią lub zdaniem sprzecznym.

Zadanie 1.3 Pokaż, że jeśli <p(po, ■ ■ ■ ,p_n) jest tautologią oraz że ipo, ...ip_n są dowolnymi zdaniami, to zdanie <p(ipo,..., ip_n) jest również tautologią.

Zadanie 1.4 Niech ipo = p oraz <Pn+i = {‘Pn) —> P dla liczb naturalnych n. Dla jakich liczb naturalnych n zdanie p_n jest tautologią?

Zadanie 1.5 (Liczby Catalana) Niech c_n oznacza liczbę sposobów którymi można rozmieścić nawiasy w iloczynie x\... x_n. Przyjmujemy, że cq=0. Oczywiście c\ = C2 = 1. Wyznacz wartości C3 i C4 Pokaż, że

= (1.1)

i—0

Zadanie 1.6 Ile istnieje nierównoważnych formuł rachunku zdań zbudowanych ze zmiennych zdaniowych p, q?

Zadanie 1.7 Pokaż, że za pomocą koniunkcji i alternatywy nie można zdefiniować negacji. Pokaż, że za pomocą alternatywy i koniunkcji nie można zdefiniować implikacji

Zadanie 1.8 Pokaż, że liczba 0.101001000100001000001.. .jest niewymierna. Przeprowadź analizę przedstawionego dowodu.