- •Оглавление
- •Глава 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. Исчисление предикатов
- •Литература
- •Предметный указатель
Определения кванторных высказываний
|
|
Утвердительные высказывания |
Отрицательные высказывания |
|
| ||
Общие высказывания |
положительный смысл |
[Верно, что]* для всех x выполняется свойство P |
xP(x)=И |
xP(x)=И |
[Верно, что] для всех x не выполняется свойство P |
положительный смысл |
Общие высказывания |
[Верно, что] не существует x, для которого не выполняется свойство P |
xP(x)=И |
xP(x)=И |
[Верно, что] не существует x, для которого выполняется свойство P | ||||
отрицательный смысл |
Не верно, что не для всех x выполняется свойство P |
xP(x)=Л |
xP(x)=Л |
Не верно, что не для всех x не выполняется свойство P |
отрицательный смысл | ||
Не верно, что существует x, для которого не выполняется свойство P |
xP(x)=Л |
xP(x)=Л |
Не верно, что существует x, для которого выполняется свойство P |
Окончание табл. 8
|
|
Утвердительные высказывания |
Отрицательные высказывания |
|
| ||
Частные высказывания |
положительный смысл |
[Верно, что] существует x, для которого выполняется свойство P |
xP(x)=И |
xP(x)=И |
[Верно, что] существует x, для которого не выполняется свойство P |
положительный смысл |
Частные высказывания |
[Верно, что] не для всех x не выполняется свойство P |
xP(x)=И |
xP(x)=И |
[Верно, что] не для всех x выполняется свойство P | ||||
отрицательный смысл |
Не верно, что не существует x, для которого выполняется свойство P |
xP(x)=Л |
xP(x)=Л |
Не верно, что не существует x, для которого не выполняется свойство P |
отрицательный смысл | ||
Не верно, что для всех x не выполняется свойство P |
xP(x)=Л |
xP(x)=Л |
Не верно, что для всех x выполняется свойство P |
* Слова «верно, что» могут быть опущены.
4.1. Алгебра логики предикатов
Алфавит логики предикатов содержит следующие символы:
символы предметных переменных – обычно строчные латинские буквы с индексами или без них;
символы предикатов – обычно прописные латинские буквы с индексами или без них;
логические символы: ,,,,;
символы кванторов – ,;
скобки и запятую.
Слово в алфавите логики предикатов называется формулой, если оно удовлетворяет следующему индуктивному определению:
если P– символ предиката,x1,x2,...,xn– символы предметных переменных, тоP(x1,x2,...,xn) – формула. Такая формула называетсяатомарной. Все предметные переменные атомарных формул свободные, связанных переменных нет;
пусть A– формула. ТогдаAтоже формула. Свободные и связанные переменные формулыA– это соответственно свободные и связанные переменные формулыA;
пусть AиB– формулы, причем нет таких предметных переменных, которые были бы связаны в одной формуле и свободны в другой. ТогдаAB,AB,AB,ABесть формулы, в которых свободные переменные формулAиBостаются свободными, а связанные переменные формулAиBостаются связанными;
пусть A– формула, содержащая свободную переменнуюx. ТогдаxA,xA тоже формулы, переменнаяxв них связана. Остальные переменные, которые в формулеAсвободны, остаются свободными, а переменные, которые в формулеAсвязаны, остаются связанными. Говорят, что формулаAестьобласть действия квантора;
слово в алфавите логики предикатов 1–5 является формулой только в том случае, если это следует из правил 1–4;
Заметим, что по определению формулы никакая переменная не может быть одновременно свободной и связанной.
Значение формулы определено лишь тогда, когда задана какая-нибудь интерпретация (модель) входящих в нее символов, т.е. система D=<M,f >, состоящая из непустого множестваMи соответствия f, которое для каждого предикатного символа P(n)определяетn‑местный предикат.