Главная   Онлайн инструменты по математической логике   Мат. логика теория   Как считает компьютер?   Схемы для ЭВМ    

Предикаты

Определение булевой функции
Элементарные булевы функции
Задание булевых функций посредством элементарных
Существенные и несущественные переменные
Эквивалентные функции
Основные эквивалентности
Функциональная полнота
Нормальные формы
Совершенные нормальные формы
Минимизация ДНФ методом Квайна
Карты Карно
Полином Жегалкина
Высказывания
Предикаты
Кванторы
Определение формальной теории
Исчисление высказываний
Теорема о дедукции. Полнота ИВ
Автоматическое доказательство теорем
Метод резолюций в ИВ
Определение алгоритма
Машина Тьюринга
Рекурсивные функции
Алгоритмически неразрешимые задачи
Алгоритмы и их сложности



     Предметом изучения в этой главе будут предикаты — отображения произвольных множеств во множество высказываний. Фактически, мы совершаем переход на новый уровень абстракции, переход такого типа, какой был совершен в школе — от арифметики вещественных чисел к алгебре числовых функций.
     Определение. Пусть X1,X2 ... Xn — символы переменных произвольной природы. Эти переменные будем называть предметными. Пусть наборы переменных (X1,X2 ... Xn) принадлежат множеству M=(M1,M2 ... Mn), которое будем называть предметной областью (т.е. Xi∈Mi, где Мi называются областью определения переменной Xi). Предикатом местности n (n-местным предикатом), определенным на предметной области M, называют логическую функцию принимающую либо значение И либо значение Л.
     Пример 1. D(x1,x2) = «Натуральное число х1 делится (без остатка) на натуральное число х2» — двуместный предикат, определенный на множестве пар натуральных чисел M=N N. Очевидно, D(4,2) = И, D(3,5) = 0.
     Пример 2. Q(x) == «x2<-1, х∈R» — одноместный предикат, определенный на множестве действительных чисел М=R. Ясно, что Q(-1) = Л, Q(5) = Л, и вообще предикат Q(x) — тождественно ложен, т. е. Q(x) = Л для всех х∈R.
     Пример 3. В(x,у,z) = «х2+y2<z; х,у,z∈R» — трехместный предикат, определенный на R3. В(1,1,-2)=Л, В(1,1,2)=И.
     Предикат Р, определенный на M, называется тождественно истинным, если он принимает значение И при любых значениях предметных переменных; Предикат Р называется тождественно ложным, если он принимает значение Л при любых значениях предметных переменных. Предикат Q из примера 2 является тождественно ложным.
     Поскольку предикаты — это функции со значениями во множестве высказываний, где введены логические операции, то эти операции естественно определяются и для предикатов. Пусть P и Q — предикаты, определенные на M. Тогда:
     1. ¬P(x1,x2 ... xn)=¬(P(x1,x2 ... xn))
     2. (P&Q)(x1,x2 ... xn)=P(x1,x2 ... xn)&Q(x1,x2 ... xn)
     3. (PvQ)(x1,x2 ... xn)=P(x1,x2 ... xn)vQ(x1,x2 ... xn)
     4. (P→Q)(x1,x2 ... xn)=P(x1,x2 ... xn)→Q(x1,x2 ... xn)
     Предикаты Р и Q, определенные на M, называются равносильными (пишут Р=Q), если P(x1,x2 ... xn)=Q(x1,x2 ... xn) для любого набора (x1,x2 ... xn) предметных переменных из M.
     Теорема. Множество n-местных предикатов, определенных на M, образует булеву алгебру предикатов. Т.е. для них справедливы основные эквивалентности.

@ 2010 - 2017 tablica-istinnosti.ru Рейтинг@Mail.ru