Новини освіти і науки:

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

Повні та неповні набори логічних зв’язок.

Приклади

Диз’юнктивні та кон’юнктивні нормальні форми.

Істинною функцією від n аргументів будемо називати функцію від n аргументів, яка приймає значення И або Л, якщо її аргументи приймають ті ж значення.

Таблиця істинності для функції n змінних містить рядків. Кожний рядок містить деякий розподіл істинних значень для аргументів і відповідне значення функції. Наприклад:


и	и	и
и	л	л
л	и	л
л	л	и

Покажемо як, маючи таблицю істинності, побудувати за нею відповідну ПФорму. Рядки таблиці пронумеруємо . Вибираємо тільки ті рядки, для яких . Нехай перший такий рядок має номер . За цим рядком побудуємо кон’юнкцію , де – це , якщо в цьому рядку має значення И, а - це , якщо в цьому рядку має значення Л.

Так ми чинимо з усіма рядками, в яких значення . Отримуємо кон’юнкцію . Беремо диз’юнкцію . В результаті отримуємо ПФорму, яка відповідає даній таблиці істинності (говоримо, що ПФорма породжує задану істинну функцію). Цю ПФ називають диз’юнктивною нормальною формою (ДНФ).

Для нашого приклада:

Для першого рядка

Для четвертого рядка

ДНФ:

	&		V		&
И	И	И	И	Л	Л	И
И	Л	Л	Л	Л	Л	Л
Л	Л	И	Л	И	Л	И
Л	Л	Л	И	И	И	Л

Означення. Пропозиційну форму називаємо диз’юнктивною нормальною формою (ДНФ), якщо вона є диз’юнкцією, яка містить один чи більше диз’юнктивних членів, кожний з яких є диз’юнкцією однієї чи більше пропозиційних літер чи їх заперечення.

Означення. Пропозиційну форму називаємо кон’юнктивною нормальною формою (КНФ), якщо вона є кон’юнкцією, яка містить один чи більше кон’юнктивних членів, кожний з яких є кон’юнкцією однієї чи більше пропозиційних літер чи їх заперечення.

Зауважимо, що в цих означеннях ПЛітеру та її заперечення ми розглядаємо як (вироджену) V або &.

ДНФ: ;

КНФ: .

За таблицею істинності для істинної функції можна побудувати ПФ, яка є КНФ.

Кожній пропозиційній формі відповідає її таблиця істинності. Кожній істинній функції (тобто таблиці істинності) відповідає ДНФ.

Будемо говорити, що набір логічних зв’язок повний, якщо для кожної істинної функції існує ПФ, яка містить зв’язки лише з цього набору, яка її визначає.

Значить, набір логічних зв’язок - повний.

Теорема.Наступні набори логічних зв’язок є повними:

а)

б)

в)

Доведення:

а) Покажемо, що ПФ та логічно еквівалентні.

А	V	В	≡	¬	(¬	А	&	¬	В)
и	и	и	и	и	л	и	л	л	и
и	и	л	и	и	л	и	л	и	л
л	и	и	и	и	и	л	л	и	и
л	л	л	и	л	и	л	и	и	л

Отже, в силу леми 3, усяка ПФ, яка містить тільки зв’язки логічно еквівалентна деякій ПФ, яка містить тільки зв’язки (отримуваної заміною усіх виразів на ).

б) для доведення цього пункту покажемо, що ПФ та логічно еквівалентні.

А	&	В	≡	¬	(¬	А	V	¬	В)
и	и	и	и	и	л	и	л	л	и
и	л	л	и	л	л	и	и	и	л
л	л	и	и	л	и	л	и	и	и
л	л	л	и	л	и	л	и	и	л

Отже, в силу леми 3, якщо ПФ містить тільки зв’язки , то, замінимо в ПФ усі вирази на , отримаємо логічно еквівалентну ПФ, яка записана за допомогою лише двох зв’язок: .

в) для доведення цього пункту достатньо показати, що ПФ (або ) логічно еквівалентна деякій ПФ, побудованій за допомогою зв’язок .

А	V	В	≡	¬	А		В
и	и	и	и	л	и	и	и
и	и	л	и	л	и	и	л
л	и	и	и	и	л	и	и
л	л	л	и	и	л	л	л

А	&	В	≡	¬	(А		¬	В)
и	и	и	и	и	и	л	л	и
и	л	л	и	л	и	и	и	л
л	л	и	и	л	л	и	л	и
л	л	л	и	л	л	и	и	л

Теорема доведена.

Ми бачимо, що існують пари зв’язок (наприклад: ¬ та &), через які можуть бути виражені усі істинні функції.

Виявляється, що існує логічна зв’язка (одна), за допомогою якої можна домогтися того ж ефекту.

Логічна зв’язка – штрих Шеффера - це бінарна зв’язка з істинною таблицею:

А	В	А\|В
и	и	л
и	л	и
л	и	и
л	л	и

Теорема. Штрих Шеффера повний, тобто є повним набором.

Доведення:

Відомо, що набір - повний. Тавтологіями є такі еквіваленції:

¬	А	≡	А	\|	А
л	и	и	и	л	и
и	л	и	л	и	л

А	V	В	≡	(А	\|	А)	\|	(В	\|	В)
и	и	и	и	и	л	и	и	и	л	и
и	и	л	и	и	л	и	и	л	и	л
л	и	и	и	л	и	л	и	и	и	и
л	л	л	и	л	и	л	и	л	и	л

Логічна зв’язка – стрілка Пірса {↓} – це бінарна зв’язка з істинною таблицею:

А	В	А↓В
и	и	л
и	л	л
л	и	л
л	л	и

Теорема. Стрілка Пірса є повним набором.

Доведення:

Відомо, що набір – повний. Тавтологіями є такі еквіваленції:

¬	А	≡	А	↓	А
л	и	и	и	л	и
и	л	и	л	и	л

А	&	В	≡	(А	↓	А)	↓	(В	↓	В)
и	и	и	и	и	л	и	и	и	л	и
и	л	л	и	и	л	и	л	л	и	л
л	л	и	и	л	и	л	л	и	л	и
л	л	л	и	л	и	л	л	л	и	л

Інших повних наборів (крім та {↓}) з одної зв’язки немає. Доведемо це.

Теорема. Єдиними бінарними зв’язками, кожної з яких достатньо для побудови усіх істинних функцій, є зв’язки | та ↓.

Доведення:

Припустимо, що існує деяка бінарна зв’язка * така, що цієї зв’язки достатньо для побудови усіх істинних функцій.

Припустимо, що, якщо А=В=И, то А*В=И. Тоді будь-яка ПФ, яка побудована тільки за допомогою зв’язки *, приймала б значення И, якщо усі, які входять в її запис ПЛітери приймають значення И. Отже, форма ¬А не могла би бути виражена тільки через зв’язку *. Тому И*И=Л.

Аналогічно отримаємо, що Л*Л=И. Таблиця істинності:

А	В	А*В
и	и	л
и	л
л	и
л	л	и

Якщо друге та третє місце в таблиці значень А*В займають значення И, И, то * - це штрих Шеффера, якщо значення Л, Л, то * - це стрілка Пірса.

Якщо Л, И, то (А*В) логічно еквівалентна ¬А, якщо И, Л, то ПФ (А*В) логічно еквівалентна ¬В.

А	*	В	≡	¬	А
и	л	и		л	и
и	л	л		л	и
л	и	и		и	л
л	и	л		и	л

А	*	В	≡	¬	В
и	л	и		л	и
и	л	л		и	л
л	и	и		л	и
л	и	л		и	л

В обох випадках (А*В) виражена через заперечення. Але невірно, що, використовуючи зв’язку ¬, ми можемо для будь-якої ПФ записати логічно еквівалентну. Єдиними істинними функціями від однієї змінної, які можуть бути виражені через ¬, є: функція, тотожно рівна саме змінній , та заперечення змінної.


и	и
л	л


и	л
л	и

←ПФ:

ПФ: →
А, наприклад, функція тотожно рівна И невиразна через заперечення.

В Логіці висловлювання ми використовуємо зв’язки ( не використовуємо).

Обговоримо набори, які складаються з двох зв’язок. Ми вже знаємо, що набори повні.

Набори не є повними.

Для наборів, за виключенням набору , доведення неповноти проводиться однаково.

Доведемо, що - неповний набір. Достатньо показати, що для ПФ неможливо побудувати логічно еквівалентну ПФ, використовуючи лише зв’язки . Розглянемо ПФ, які містять одну логічну зв’язку: , .

ПФ: - логічно еквівалентна А

А	&	А	≡А
и	и	и
л	л	л

ПФ: логічно еквівалентна А

А	V	А	≡А
и	и	и
л	л	л

Доведемо, що будь-яка ПФ від однієї ПЛітери А, яка побудована за допомогою зв’язок логічно еквівалентна А. Якщо це так, то ПФ ( логічно не еквівалентна А) неможливо записати, використовуючи зв’язки .

Доведення проводимо індукцією по числу l логічних зв’язок, які входять в запис ПФ А.

1. Базис індукції. Якщо l=1, то А – це або А – це , цей випадок ми вже розглядали .

2. Індуктивний крок. Припустимо, що твердження доведено для l=k, тобто для всякої ПФ А(А), яка містить не більш k зв’язок . Нехай та - такі ПФ.

Доведемо твердження для l=k+1.

Розглянемо , - кожна з цих форм логічно еквівалентна А, що і треба було.

Доведемо, що - неповний набір.

Достатньо показати, що для ПФ ¬А неможливо побудувати логічно еквівалентну ПФ, використовуючи лише зв’язки . Розглянемо ПФ, яка містить одну зв’язку: , .

А		А
и	и	и
л	и	л

← це тавтологія,

А	≡	А
и	и	и
л	и	л

← і це тавтологія.

Доведемо, що будь-яка ПФ від однієї ПЛ А, яка побудована за допомогою зв’язок , є тавтологією (і тоді ¬А неможливо записати, використовуючи зв’язки ).

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Леми про тавтології	\|	Формальна аксиоматична теорія L для числення висловлювань.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.008 сек.