- •Оглавление
- •Глава 3. Логика высказываний 78
- •Глава 4. Логика предикатов 90
- •Введение
- •I. Системы счисления
- •1.1. Непозиционные системы счисления. Римская система счисления
- •1.2. Позиционные системы счисления
- •1.3. Взаимосвязь систем счисления
- •I. Алгоритм перевода целого числа Aq из q-ичной системы счисления в число Bd d-ичной системы
- •II. Алгоритм перевода целого числа Ad из d-ичной системы счисления в число Bq q-ичной системы
- •III. Алгоритм перевода правильных дробей из q-ичной системы счисления в d-ичную с вычислениями в d-ариф-метике
- •IV. Алгоритм перевода правильных дробей из d-ичной системы счисления в q-ичную с вычислениями в d-арифметике
- •V. Алгоритм перевода чисел из d-ичной системы счисления в dn-ичную систему счисления
- •VI. Алгоритм перевода чисел из dn-ичной системы счисления в d-ичную систему счисления.
- •1.4. Двоичная система счисления
- •1.4.1. Двоичная арифметика
- •1.4.3. Вычитание с использованием двоичного дополнения. Умножение
- •Алгоритм вычитания целых десятичных чисел
- •Алгоритм отыскания двоичного дополнения числа
- •Теория множеств
- •Глава 1. Множества
- •1.1. Основные определения
- •1.2. Основные операции теории множеств
- •Старшинство операций (операции даны по убыванию приоритетов)
- •1.4. Диаграммы Венна
- •1.5. Основные законы теории множеств
- •1.6. Декартово произведение и отношения
- •Глава 2. Бинарные отношения
- •2.1. Основные определения
- •Глава 3.Функции и операции
- •Примеры функций
- •Операции над функциями
- •Свойства бинарных операций
- •Глава 4.Алгебраические структуры
- •III. Математическая логика
- •Глава 1. Переключательные функции
- •1.1. Основные определения
- •Переключательные функции двух аргументов
- •1.2. Основные теоремы (эквивалентные соотношения) переключательных функций
- •Глава 2.Булева алгебра
- •2.1. Основные определения
- •Эквивалентные соотношения в булевой алгебре
- •2.2. Минимизация булевых функций
- •2.3. Аналитические методы нахождения мднф Метод Квайна
- •Формулы метода
- •Алгоритм метода
- •Метод Блейка
- •Формулы метода
- •Алгоритм метода
- •Сравнение методов Квайна и Блейка
- •Построение мднф из Сокр.Днф с помощью таблицы Квайна
- •Алгоритм получения fМднФс помощью таблицы Квайна
- •2.4. Графическая минимизация логических функций
- •Метод карт Карнапа
- •Алгоритм минимизации по карте Карнапа
- •2.5. Полнота систем булевых функций
- •Классы Поста
- •Полиномы Жегалкина
- •Глава 3.Логика высказываний
- •3.1. Основные понятия
- •3.2. Алгебра логики высказываний
- •3.3. Применение к естественному языку
- •Список наиболее часто встречающихся выражений, соответствующих логическим связкам
- •3.4. Исчисление высказываний (ив)
- •Глава 4.Логика предикатов
- •Определения кванторных высказываний
- •4.1. Алгебра логики предикатов
- •4.2. Выполнимость и общезначимость
- •4.3. Равносильность формул
- •Приведенные формулы
- •4.4. Применение логики предикатов к естественному языку
- •4.4.1. Суждения
- •Виды категорических суждений
- •4.4.2. Исчисление одноместных предикатов как исчисление классов. Теория категорических суждений и силлогизмов Аристотеля
- •Законы формальной логики Аристотеля:
- •4.4.3. Умозаключения
- •Наиболее распространенные схемы правильных дедуктивных рассуждений
- •4.4.4. Основные законы формальной логики. Логические основы аргументации
- •4.5. Исчисление предикатов
- •Литература
- •Предметный указатель
4.3. Равносильность формул
Пусть формулы Fи Gимеют одно и то же множество свободных переменных, тогда:
– Fи Gравносильны(эквивалентны) в данной модели, если на любом наборе значений свободных переменных они принимают одинаковые значения.
– Fи Gравносильны (эквивалентны) на множестве M, если они равносильны во всех моделях, заданных на множествеM.
– F и G равносильны (эквивалентны) (в логике предикатов), если они равносильны на всех множествах (тогда будем писать F=G).
Пример 38.Пусть на множествеM={a,b} заданы предикатыP1(x,y) иP2(x,y):
x |
y |
P1(x,y) |
P2(x,y) |
a |
a |
И |
И |
a |
b |
Л |
И |
b |
a |
Л |
Л |
b |
b |
И |
Л |
Рассмотрим две формулы
Q(x1,x2)Q(x1,x3), (1)
Q(x1,x2)Q(x2,x3). (2)
Если основным множеством модели служит множество Mи формула Qинтерпретируется как предикат P1, то формулы (1) и (2) равносильны в этой модели, так как принимают значение И только на двух наборах свободных переменных <a,a,a> и <b,b,b>.
x1 |
x2 |
x3 |
P1(x1, x2) |
P1(x1, x3) |
P1(x2, x3) |
Q = P1 |
P2(x1, x2) |
P2(x1, x3) |
P2(x2, x3) |
Q = P2 | ||
(1) |
(2) |
(1) |
(2) | |||||||||
a |
a |
a |
И |
И |
И |
И |
И |
И |
И |
И |
И |
И |
a |
a |
b |
И |
Л |
Л |
Л |
Л |
И |
И |
И |
И |
И |
a |
b |
a |
Л |
И |
Л |
Л |
Л |
И |
И |
Л |
И |
Л |
a |
b |
b |
Л |
Л |
И |
Л |
Л |
И |
И |
Л |
И |
Л |
b |
a |
a |
Л |
Л |
И |
Л |
Л |
Л |
Л |
И |
Л |
Л |
b |
a |
b |
Л |
И |
Л |
Л |
Л |
Л |
Л |
И |
Л |
Л |
b |
b |
a |
И |
Л |
Л |
Л |
Л |
Л |
Л |
Л |
Л |
Л |
b |
b |
b |
И |
И |
И |
И |
И |
Л |
Л |
Л |
Л |
Л |
Если основным множеством модели является то же множество M, но формула Qинтерпретируется как предикат P2, то формулы (1) и (2) не равносильны, так как на наборе <a,b,b> формула (1) принимает значение И, а формула (2) – Л.
В общем случае, прямой перебор всех значений переменных может быть невозможен, если предметные переменные имеют бесконечные области определения. Поэтому в логике предикатов используются различные косвенные приемы, в том числе эквивалентные соотношения, позволяющие выполнить корректные преобразования предикатных формул.
В логике (алгебре) предикатов справедливы все эквивалентные соотношения логики (алгебры) высказываний, а также собственные эквивалентные соотношения, включающие связки и :
1. а) xyP(x,y)=yxP(x,y), б)xyP(x,y)=yxP(x,y).
2. а) xyP(x,y)yxP(x,y), б)yxP(x,y)xyP(x,y).
3. а) xP(x)=xP(x), б)xP(x)=xP(x).
4. xP(x)xQ(x)=x(P(x)Q(x)), но
xP(x)xQ(x)x(P(x)Q(x)).
5. xP(x)xQ(x)=x(P(x)Q(x)), но
xP(x)xQ(x)x(P(x)Q(x)).
6. Если в формуле Cнет свободной переменнойx, то:
а) xP(x)C=x(P(x)C), б)xP(x)C=x(P(x)C).
в) xP(x)C=x(P(x)C), г)xP(x)C=x(P(x)C).
Приведенные формулы
Формулы, в которых из логических символов имеются только символы ,,, причем символвстречается лишь перед символами предикатов, будем называтьприведенными формулами. Для любой формулы существует равносильная ей приведенная формула, которая имеет те же множества свободных и связанных переменных.
Приведенная формула называется нормальной(илипрефиксной нормальной), если она не содержит символов кванторов или все символы кванторов стоят в начале формулы (т.е. логические символы и символы предикатов стоят в области действия каждого квантора).
Для любой приведенной формулы существует равносильная ей нормальная формула той же длины. Такая формула называется нормальной формойданной приведенной формулы.
Пример 39. Получить нормальную форму с минимальным количеством связанных переменных для формулы.
.
Номера над знаками равенства соответствуют номерам эквивалентных соотношений.