Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Matematicheskaya_logika_i_teoria_algoritmov.docx
Скачиваний:
3
Добавлен:
01.07.2025
Размер:
1 Мб
Скачать
☆

1.7. Отношение следования.

Определение 5: Следование формулы В из формулы А будем обозначать:

1) Формула В следует из формулы А если в любой интерпретации, в которой формула А истинна, формула В также истинна.

Пример

Чтобы в этом убедиться, необходимо построить таблицу истинности.

2) Формула А следует из множества формул Г= если во всех интерпретациях, в которых формулы истинны, формула А также истинна.

, … И

(Здесь и далее символ будет соответствовать словесной формулировке «если…, то…»)

Пример

Убедиться можно аналогично, построив таблицу истинности.

Теорема 1: Теорема о следовании и импликации.

(Здесь и далее символ будет соответствовать словесной формулировке «тогда и только тогда»)

Необходимость:

т.к. , ,

или ,

Достаточность:

Значит ,

Обобщение теоремы 1:

Г, Г , где Г=

Следствие теоремы 1:

- формула B следует из множества формул A тогда и только тогда, когда формула A – общезначима. Таким образом, следование равнозначно, когда некая другая формула является общезначимой.

1.8. Равносильность.

Определение 6: Равносильность формулы В формуле А будем обозначать АВ

Формула А равносильна формуле В, если в любой интерпретации I. В случае логики высказываний формулы равносильны, если их таблицы истинности одинаковы, что используется для доказательства равносильности.

Основные формулы равносильности:

1)А А – идемпотентность;

2) , – коммутативность;

3) – ассоциативность;

4) – дистрибутивность;

5)Законы де Моргана

Для алгебры предикатов необходимо добавить закон коммутативности для кванторов:

и законы де Моргана для кванторов

Теорема 2. Отношение равносильности связано с отношением следования:

А  B

Необходимость: Пусть AB, то

или

Достаточность: (в обратную сторону) и , и когда , то и AB.

Теорема 3. Связывает отношение равносильности с операцией эквивалентности:

AB

Следствие: AB, BC ( , )

Теорема 4. Теорема об эквивалентной замене:

Если AB и есть C, в которое A входит в качестве подформулы,

CB – формула, в которой все вхождения формулы А заменены на формулу В.

Эта теорема позволяет изменять цепочки формул без изменения их истинностного значения.

Пример:

2. Булевы функции и нормальные формы.

Логическими функциями называются функции от булевых переменных, значения которых есть булева величина. Логическое выражение: Bn B

2.1. Способы задания.

Задание логической функции с помощью таблицы.

Каждая логическая функция может быть задана с помощью таблицы.

Пример: Задана некая булева функция.

X

Y

Z

F(x,y,z)

0

0

0

1

0

0

1

0

0

1

0

1

0

1

1

0

1

0

0

1

1

0

1

0

1

1

0

1

1

1

1

1

Всего 2n логических наборов переменных (комбинаций).

Сколько может быть различных булевых функций от n переменных?

2n-количество различных упорядоченных наборов из n переменных. Логическая функция от n переменных может быть задана как 2n различных наборов, при этом каждому набору должно соответствовать одно из двух значений.

Таким образом, при n=1, получаем 22=4 логических функций f(x).

x

x

0

1

0

1

0

1

1

0

0

1

При n=2 ,получаем 16 функций.

x

y

(x)

(y)

x

y

0

1

|

0

0

0

0

1

1

0

1

0

0

1

1

0

0

0

1

1

1

0

1

0

1

1

0

0

1

0

1

1

0

0

1

1

0

1

0

1

0

1

0

0

1

0

1

0

1

0

0

1

0

1

1

1

0

1

1

1

1

0

0

0

1

1

1

1

1

0

0

0

1

0

0

(x)– константа х (y)– константа y

x – отрицание х y – отрицание y

0 – константа 0 1 – константа 1

- конъюнкция – Дизъюнкция

- Импликация - эквивалентность

- сравнение x>y - сравнение x<y

- исключающее или - обратная импликация

| - штрих Шеффера («И НЕ») - стрелка Пирса («ИЛИ НЕ»)

Задание логической функции с помощью формулы.

Логическую функцию можно задать с помощью формул и бинарных операций.

Пример:

У нас есть некая бинарная функция и.

Если вместо одной из переменных поставить любую бинарную функция, то получим функцию от 3-х переменных.

Вывод: любая функция может быть задана как таблицей, так и формулой.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]