Элементы математической логики. Фролов И.С. - 28 стр.

UptoLike

Составители:

Рубрика:

нулевой набор для G должен быть нулевым набором и для F . Но это

равносильно тому, что множество конъюнктивных членов G содержит-

ся в множестве конъюнктивных членов F . 

Пример 8. Найдем все логические следствия формулы

A ⇒ B ∧ C. По таблице значений (см. пример 6) составим СКНФ :

(¬A ∨ B ∨ C) ∧(¬A ∨ B ∨ ¬C) ∧ (¬A ∨ ¬B ∨ C).

Отсюда заключаем, что логическими следствиями данной формулы яв-

ляются отдельные конъюнктивные члены

¬A ∨ B ∨ C ∼ A ⇒ B ∨ C, ¬A ∨ B ∨ ¬C ∼ A ∧ C ⇒ B,

¬A ∨ ¬B ∨ C ∼ A ∧ B ⇒ C,

а также их попарные конъюнкции

¬A ∨ B ∼ A ⇒ B, ¬A ∨ C ∼ A ⇒ C,

¬A ∨ ((B ∨ ¬C) ∧ (¬B ∨ C)) ∼ A ⇒ (B ⇔ C).

В полный перечень логических следствий входят также исходная фор-

мула и тождественно истинная формула.

§4. Функциональная полнота

и замкнутость

1. Функционально полные системы функций

Существует два существенно различных способа задания логиче-

ских функций — табличный и формульный. Таблица задает непосред-

ственное соответствие между значениями аргумента и функции. Фор-

мула — более компактный способ задания функции, однако он задает

функцию через другие функции.

Пусть Σ — некоторая система логических функций, Σ ⊂ Λ (Λ —

множество всех логических функций). Нас будут интересовать следу-

ющие два вопроса: Всякая ли логическая функция может быть пред-

ставлена формулой над Σ ? И если нет, то какие логические функции

могут быть представлены формулами над Σ ?

С помощью эквивалентностей записываем их в виде импликаций.

Записанные сразу в упрощенном виде.