81839 Scan0008 (2)

1.5 Funkcjonalna pełność 15

1.4.2 Przykłady formuł logicznie równoważnych

prawo podwójnego przeczenia

AV1 = 1    dAUd 1

AV0 = A    A AOeeO j

AvA = A AaA = A A V ~ A = 1 A A ~ A = 0

~ (yl V 13)    1

~ (.A A 13) = ~ A V ~ B J A A (B V C) = (A A B) V (A A C) A V (B A C) = (A V B) A (A V C)

prawa identyczności

prawa idempotentności prawo wyłączonego środka prawo sprzeczności

prawa de Morgana j- prawa rozdzielności

Przykład 1.3 Uproście formułę p A (~ p V q).

p A (~ p V q) = (p A ~ p) V (p A g) = 0 V (p A q) = p A q.

1.5 Funkcjonalna pełność

Zbiór funktorów jedno- i dwuargumentowych jest redundantny, tzn. za pomocą pewnego jego podzbioru można zdefiniować wszystkie pozostałe funktory.

Definicja 1.5 Zbiór funktorów nazywamy funkcjonalnie pełnym, jeżeli dowolne zdanie możemy zapisać tylko za pomocą funktorów z tego zbioru.

Zbiorami funkcjonalnie pełnymi są, np.: {V, A, {V,~}₅ {A,~}, {=©~}. Dysjunkcja Sheffera i binegacja tworzą oddzielnie minimalne zbiory funkcjonalnie pełne {)}, {J,}.

Przykład 1.4

• p=>ę = ~pVę=~(pA~g),