Элементы математической логики

Министерство образования Московской области Государственное бюджетное образовательное учреждение среднего профессионального образования Московской области «Балашихинский промышленно-экономический колледж» И.А. КАВЕРИНА Курс лекций по элементам математической логике Балашиха 2014 г. Каверина И.А. Курс лекций по элементам математической логике. Учебнометодическое пособие. - Балашиха: Балашихинский промышленно- экономический колледж, 2014, 65 с. Пособие разработано государственного в соответствии образовательного с требованиями стандарта по курсу федерального «Элементы математической логики». Для студентов среднего профессионального образования по специальности 230115 «Программирование в компьютерных системах». Библиогр. 9 назв. Составитель: доцент, к.ф.-м.н. И.А. Каверина 1 Введение Зададимся вопросом: «для чего программисту нужен данный курс?». Краткий ответ: Изучение его преследует две цели – изучить логические основы процесса написания программ и приобрести навыки строгого, формализованного мышления. А теперь более подробно. Математика является наукой, в которой все истины доказывают с помощью умозаключений. Поэтому для математики большое значение имеют логические теории как средства построения математических знаний (logos (греч.) – слово, понятие, рассуждение, разум). Логика – это наука, изучающая методы доказательств и опровержений, то есть методы установления истинности или ложности одних высказываний (утверждений) на основе истинности или ложности других. Рассмотрим вкратце этапы развития логики. 1-й этап. Как самостоятельная наука логика оформилась в трудах Аристотеля (IVв. до н.э.). Он пытался найти ответ на вопрос ”как мы рассуждаем”, изучал ”правила мышления”. Аристотель впервые дал систематическое изложение логики. В результате возникла формальная теория, связана с анализом наших обычных содержательных умозаключений, выражаемых разговорным языком, которая впоследствии стала называться формальной или Аристотелевой логикой. Правила вывода, описанные Аристотелем (силлогизмы), были основным инструментом логики вплоть до 17в. Силлогизм - это рассуждение, в котором из заданных двух суждений выводится третье. Например: 1) Все млекопитающие имеют скелет. Все киты – млекопитающие. Следовательно, все киты имеют скелет. 2) Все квадраты ромбы, все ромбы – параллелограммы. 2 Следовательно, все квадраты – параллелограммы. В общем виде этот силлогизм имеет форму: ”Все A суть B, все B суть C. Следовательно, все A суть C.” А вот пример силлогизма неправильной формы: Все квадраты – ромбы. Некоторые ромбы имеют острый угол. Следовательно, некоторые квадраты имеют острый угол. Значит, силлогизм, имеющий форму ”Все A суть B, некоторые B суть C. Значит, некоторые A суть C ” может привести и к ложным выводам. Аристотель выделил все правильные формы силлогизмов, которые можно составить из рассуждений вида: "Все A суть B"; "Некоторые A суть B"; "Все A не суть B"; "Некоторые A не суть B". 2-й этап. Однако, развитие математики выявило недостаточность формальной логики, поэтому в конце 17в. Г.Лейбниц предложил понятия логики обозначить символами, которые соединялись бы по особым правилам. Это позволяло всякое рассуждение заменить вычислением. Первая реализация идей Г.Лейбница принадлежит английскому математику Дж.Булю (1815-1864). Он создал алгебру, в которой буквами обозначены высказывания, и это привело к алгебре высказываний (или булевой алгебре). Именно благодаря введению символов в логику была получена основа для создания новой науки – математической логики. Математическая логика – это современная форма логики, которая полностью опирается на формальные математические методы. Применение математики к логике позволило представить логические теории в новой удобной форме и применить вычислительный аппарат к решению задач, малодоступных человеческому мышлению. 3-й этап связан с XX веком и попытками обосновать справедливость математических доказательств, с исследованиями теории чисел, а также с попыткой разрешить известные логические парадоксы. 3 Самым знаменитым следует считать парадокс лжеца, известный еще со времен глубокой древности: Некто говорит: ’’я лгу’’. Если он при этом лжет, то сказанное им есть ложь, и, следовательно, он не лжет. Если же он не лжет, то сказанное им есть истина, и следовательно, он лжет. В любом случае оказывается, что он лжет и не лжет одновременно. Развитие математической логики особенно активизировалось в XX нашего века в связи с развитием вычислительной техники и программирования. Очевидно, что компьютерные науки носят прикладной характер и конечной их целью является создание и использование вычислительных систем. Здесь теоретические знания подтверждаются идеями воплощенными в ”железе” и в получении результатов по обработке информации. Поэтому для инженера, программиста, математическая вычислениях, обоснованных логика является алгоритмах, наукой надежно о правильных функционирующих программах. Она не рассматривает вопросы проектирования программ, но изучает языки программирования как формальные системы и касается аспектов эффективности тех или иных алгоритмов. В учебном пособии излагается материал по математической логике, изучаемый в курсе «Элементы математической логики» и предназначенный для специальности 230115 «Программирование в компьютерных системах». 4 Глава I. Алгебра логики §1.1. Определение булевой функции Булевой функцией y=f(x1,x2,…,xn) от п переменных x1,x2,...,xn называется любая функция, в которой аргументы и функция могут принимать значение либо 0 либо 1, т.е. булева функция это правило по которому произвольному набору нулей и единиц (x1,x2,...,xn) ставится в соответствие значение 0 или 1. Значение 0 часто называют Ложью (False), а значение 1 – Истинной (True). Булевы функции называются также функциями алгебры логики, двоичными функциями и переключательными функциями. Булеву функцию от n переменных можно задать таблицей истинности, в которой наборы значений аргументов расположены в порядке возрастания их номеров: сначала идет набор, представляющий собой двоичное разложение 0 (этот набор имеет номер 0); затем идет набор, являющийся двоичным разложением 1, потом 2, 3 и т.д. Последний набор состоит из n единиц и является двоичным разложением числа 2n  1 (такой порядок расположения наборов назовем лексикографическим порядком). Учитывая, что отсчет начинается с 0, а значение булевой функции может быть либо 0 либо 1, заключаем, что существует всего 22 n различных булевых функций от n переменных. Таким образом, имеется, например, 16 булевых функций от двух переменных, 256 — от трех и т. д. Пример 1.1.1. (голосование). Рассмотрим устройство, фиксирующее принятие некоторой резолюции "комитетом трех". Каждый член комитета при одобрении резолюции нажимает свою кнопку. Если большинство членов голосуют «за», то резолюция принимается. Это фиксируется регистрирующим прибором. Таким образом, устройство реализует функцию f(x,y,z), таблица истинности которой имеет вид 5 x 1 1 1 y 1 1 1 1 z 1 1 1 1 f(x,y,z) 1 1 1 Булева функция также однозначно задается перечислением всех наборов, на которых она принимает значение 0, либо перечислением всех наборов, на которых она принимает значение 1. Полученную в примере функцию f можно также задать следующей системой равенств: f(0,0,0) = f(0,0,1) = f(0,1,0) = f(1,0,0) =0. Вектором значений булевой функции y=f(x1,x2,…,xn) называется упорядоченный набор всех значений функции f, при котором значения упорядочены по лексикографическому порядку. Например, пусть функция трех переменных f задана вектором значений (0000 0010) и необходимо найти набор, на котором f принимает значение 1. Т.к. 1 стоит на 7 месте, а нумерация в лексикографическом порядке начинается с 0, то необходимо найти двоичное разложение 6. Таким образом, функция f принимает значение 1 на наборе (110). §1.2. Элементарные булевы функции Среди булевых функций особо выделяются так называемые элементарные булевы функции, посредством которых можно описать любую булеву функцию от любого числа переменных. 1. Булева функция f(x1,x2,…,xn) принимающая значение 1 на всех наборах нулей и единиц называется константой 1, или тождественной единицей. Обозначение: 1. 2. Булева функция f(x1,x2,…,xn) принимающая значение 0 на всех наборах нулей и единиц называется константой 0, или тождественным нулем. Обозначение: 0. 6 3. Отрицанием называется булева функция одной переменной, которая определяется следующей таблицей истинности x 1 f(x) 1 Обозначения: x, x . Запись x читается «не икс» или «отрицание икс». 4. Конъюнкцией называется булева функция двух переменных, которая определяется следующей таблицей истинности x 1 1 y 1 1 f(x, y) 1 Другие названия: логическое умножение (произведение); логическое «и». Обозначения: xy, xy, xy, min(x,y). Запись xy может читаться так: «икс и игрек» или «икс умножить на игрек». 5. Дизъюнкцией называется булева функция двух переменных, которая определяется следующей таблицей истинности x 1 1 y 1 1 f(x, y) 1 1 1 Другие названия: логическое сложение (сумма); логическое «или». Обозначения: xy, max(x,y). Запись xy может читаться так: «икс или игрек» или «сумма икс и игрек». 6. Импликацией называется булева функция двух переменных, которая определяется следующей таблицей истинности x 1 1 y 1 1 f(x, y) 1 1 1 Другое название: логическое следование. 7 Обозначения: xy, x  y, x  y. Запись xy может читаться так: «из икс следует игрек». 7. Эквивалентностью называется булева функция двух переменных, которая определяется следующей таблицей истинности x 1 1 y 1 1 f(x, y) 1 1 Обозначения: xy, xy,.xy. Запись xy может читаться так: «икс эквивалентно игрек» или «икс равносильно игрек». 8. Суммой по модулю_2 называется булева функция двух переменных, которая определяется следующей таблицей истинности x 1 1 y 1 1 f(x, y) 1 1 Другое название: антиэквивалентность. Обозначения: xy, x+y. Запись xy может читаться так: «икс плюс игрек». 9. Штрих Шеффера это булева функция двух переменных, которая определяется следующей таблицей истинности x 1 1 y 1 1 f(x, y) 1 1 1 Другое название: отрицание конъюнкции, логическое «не-и». Обозначение: xy. Запись xy может читаться так: «не икс или не игрек», «икс и игрек несовместны», «икс штрих Шеффера игрек». 8 10. Стрелка Пирса это булева функция двух переменных, которая определяется следующей таблицей истинности x 1 1 y 1 1 f(x, y) 1 Другое название: отрицание дизъюнкции, логическое «не-или», функция Вебба. Обозначение: xy; для функции Вебба - xy. Запись xy может читаться так: «ни икс и ни игрек», «икс стрелка Пирса игрек». Замечание. Символы , , , , , , ,  участвующие в обозначениях элементарных функций будем называть связками или операциями. §1.3. Задание булевых функций посредством элементарных Если в логическую функцию вместо переменных подставить некоторые булевы функции, то в результате получается новая булева функция, которая называется суперпозицией подставляемых функций (сложная функция). С помощью суперпозиции можно получать более сложные функции, которые могут зависеть от любого числа переменных. Запись булевых функций через элементарные булевы функции будем называть формулой реализующей данную функцию. Пример 1.3.1. Пусть задана элементарная булева функция x  y. Подставим вместо x функцию x1x2. Получаем функцию трех переменных (x1x2)y. Если вместо переменной y подставить, например, x 3x4, то получаем новую функцию от четырех переменных: (x 1x2)(x3x4). Очевидно, что таким образом мы будем получать булевы функции, которые будут выражаться через элементарные булевы функции. 9 Забегая вперед, отметим, что любая булева функция может быть представлена как суперпозиция элементарных функций. Для более компактной записи сложных функций введем следующие соглашения: 1) внешние скобки опускаются; 2) сначала производятся операции в скобках; 3) считается, что приоритет связок убывает в следующем порядке: , , , , . Для равносильных связок и оставшихся связок {,,}, следует пока расставлять скобки. Примеры 1.3.2. 1. В формуле xyz скобки расставляются следующим образом: ((xy)z), т.к. операция  сильнее операции  согласно нашему соглашению. 2. В формуле xyzx скобки расставляются следующим образом: ((xy)(zx)) 3. В формуле (xy)zxyz скобки расставляются следующим образом: ((xy)(z((xy)(z)))). 4. Формула xyz, следуя нашему соглашению, записана не корректно, т.к. расстановка скобок приводит к двум разным функциям: ((xy)z) и (x(yz)). §1.4. Существенные и несущественные переменные Булева функция y=f(x1,x2,…,xn) существенно зависит от переменной xk, если существует такой набор значений a1,a2,…,ak-1, ak+1,ak+2,…,an, что f(a1,a2,…,ak-1,0,ak+1,ak+2,…,an)  f(a1,a2,…,ak-1,1,ak+1,ak+2,…,an). В этом случае xk называют существенной переменной, в противном случае xk называют несущественной (фиктивной) переменной. Другими словами, переменная является несущественной, если ее изменение не изменяет значения функции. Пример 1.4.1. Пусть булевы функции f1(x1,x2) и f2(x1,x2) заданы следующей таблицей истинности: 10 x1 x2 f1(x1,x2) f2(x1,x2) 1 1 1 1 1 1 1 1 Для этих функций переменная x1 — существенная, а переменная x2 — несущественная. Очевидно, что булевы функции не изменяют свои значения путем введения (или удаления) несущественных переменных. Поэтому, в дальнейшем булевы функции рассматриваются с точностью до несущественных переменных (в примере можно записать: f1(x1,x2)=x1, f2(x1,x2)=x1). §1.5. Таблицы истинности. Эквивалентные функции Зная таблицы истинности для элементарных функций, можно вычислить таблицу истинности той функции, которую реализует данная формула. Пример 1.5.1. F1=x1x2(x1x2x1x2) x1 1 1 x1x2 x1x2 1 1 x2 1 1 x1x2x1x2 1 1 x1x2 1 F1 1 1 1 Таким образом, формула F1 реализует дизъюнкцию. Пример 1.5.2. F2=x1x2x1 x1 x2 x1x2 F2=(x1x2)x 1 1 1 1 1 1 1 1 1 Таким образом, формула F2 реализует константу 1. 11 Пример 1.5.3. F3=((x1x2)x1)x2. x1 x2 x1x2 (x1x2)x1 (x1x2)x1)x2 1 1 1 1 1 1 1 1 1 Таким образом, формула F3 реализует дизъюнкцию. Булевы функции f1 и f2 называются эквивалентными, если на всяком наборе (a1, a2,…, an) нулей и единиц значения функций совпадают. Обозначение эквивалентных функций следующее: f1=f2. Согласно приведенным примерам 1-3, можно написать  x1x2(x1x2x1x2)=x1x2;  x1x2x1=1;  ((x1x2)x1)x2=x1x2. §1.6. Основные эквивалентности Приводимые эквивалентности часто оказываются полезными при оперировании с булевыми функциями. Ниже H, H1, H2,… означают некоторые булевы функции. 1. Закон двойного отрицания: H  H . 2. Идемпотентность: H&H=H, HH=H. 3. Коммутативность: H1H2=H2H1, где символ  означает одну из связок &, , , , , . 4. Ассоциативность: H1(H2H3)=(H1H2)H3, где символ  означает одну из связок &, , , . 12 5. Дистрибутивность: H1&(H2H3)=(H1&H2)(H1&H3); H1(H2&H3)=(H1H2)&(H1H3); H1&(H2H3)=(H1&H2)(H1&H3). 6. Законы де Моргана: при n  2 справедливы формулы H1 & H 2 &... & H n  H1  H2  ...  Hn , H1  H 2  ...  H n  H1 & H2 &... & Hn . 7. Правила поглощения: H1(H2&H3)=H1, H1&(H2H3)=H1 8. Законы склеивания: H1 & H 2  H1 & H 2  H1 , ( H1  H 2 ) & ( H1  H 2 )  H1 . 9. Законы инверсий: H  H  1, H & H  0. 10. Правила операций с константами 0 и 1: H1=1, H&1=H, H0=H, H&0=0. Для проверки истинности приведенных эквивалентностей (кроме законов де Моргана) достаточно построить соответствующие таблицы истинности. Отметим, что свойство ассоциативности операции позволяет распространить эту операцию для любого количества переменных. Так, например, запись xуzw корректна, т.к. любая расстановка скобок приводит к одной и той же функции. Коммутативность операции позволяет менять местами переменные в формуле. Например, xyzw=wyxz. Докажем 1-й закон де Моргана H1 & H 2 &... & H n  H1  H2  ...  Hn методом математической индукции. Справедливость формулы при n  2 проверим непосредственно при помощи таблицы истинности: 13 Пусть формула верна при n  m . Тогда при n  m  1 имеем: H1 & H 2 &... & H m & H m1   H1 & H 2 &... & H m  & H m1  применяем формулу при n  2 , получаем   H1 & H 2 &... & H m   Hm1  применяем формулу при n  m , получаем =    H1  H2  ...  Hm  Hm1  H1  H2  ...  Hm1 . Из принципа математической индукции заключаем, что формула верна при любом n  2 . §1.7. Функциональная полнота В типичной современной цифровой вычислительной машине цифрами являются 0 и 1. Следовательно, команды, которые выполняет процессор, суть булевы функции. Ниже будет показано, что любая булева функция реализуется через конъюнкцию, дизъюнкцию и отрицание. Следовательно, можно построить нужный процессор, имея в распоряжении элементы, реализующие конъюнкцию, дизъюнкцию и отрицание. Этот раздел посвящен ответу на вопрос: существуют ли (и если существуют, то какие) другие системы булевых функций, обладающих тем свойством, что с их помощью можно выразить все другие функции. Введем в рассмотрение ряд классов функций. 1. Класс T0  функций, сохраняющих константу 0, т.е. таких функций y=f(x1,x2,…,xn),что f(0,0,…,0)=0. Например, xy(x). 2. Класс T1  функций, сохраняющих константу 1, т.е. таких функций y=f(x1,x2,…,xn),что f(1,1,…,1)=1. Например, x(yx). 14 3. Класс S  самодвойственных функций, т.е. таких функций y=f(x1,x2,…,xn), что f(x1,x 2 ,,x n )  f (x1,x 2 ,,x n ) . 4. Класс L  линейных функций, т.е. таких функций y=f(x1,x2,…,xn), которые могут быть представлены в виде f(x1,x2,…,xn)=c0c1x1c2x2…cnxn, где с0, c1, c2…коэффициенты, которые могут принимать значение 0 или 1. 5. Класс M  монотонных функций. На множестве наборов из нулей и единиц Вn={(x1,x2,…,xn) | xi{0,1}, i=1,2,…,n} введем частичный порядок следующим образом: (a1,,a2,...,an)  (b1,b2,...,bn) тогда и только тогда когда a1  b1, a2  b2,…,an  bn. Функция f(x1, х2,...,хn) называется монотонной, если для любых двух элементов из Вn таких, что (a1,,a2,...,an)  (b1,b2,...,bn) следует, что f(a1,,a2,...,an)  f(b1,b2,...,bn). Система F булевых функций, суперпозицией которых может быть представлена любая булева функция, называется функционально полной. Говорят, что функционально полная система F булевых функций образует базис в логическом пространстве. Базис F называется минимальным, если удаление из него любой функции превращает эту систему в неполную. Критерий полноты (Теорема Поста). Система F булевых функций является полной тогда и только тогда, когда она включает хотя бы одну функцию: не сохраняющую константу 0, не сохраняющую константу 1, не самодвойственную, нелинейную и немонотонную. Доказательство теоремы Поста приведено в приложении 1, однако для понимания ее доказательства необходимо ознакомится с главами II и III. В таблице 1.7 приведены свойства, которыми обладают элементарные булевы функции (символ * - отмечает свойство, которым обладает данная функция). 15 Таблица 1.7 Название Обо Не сохрани- Не сохранизн. мость мость константы 0 константы 1 Не Не Не Самодвойс Линей- Монотон твенность ность -ность Конст.0 Конст.1 1 * Отриц.  * Конъюн. & * * Дизъюн.  * * Имплик.  * * * Эквивал.  * * * * * * Сумма по модулю 2 Штрих Шеффера Стрелка Пирса *  * * * * *  * * * * *  * * * * * Используя теорему Поста и таблицу 1.7 можно строить базисы из элементарных функций по следующему правилу. Выбрав любую элементарную булеву функцию и дополнив ее при необходимости другими функциями так, чтобы все они вместе удовлетворяли теореме о функциональной полноте. Через функции этого базиса можно выразить все другие булевы функции. 1. Система функций S1={,,} образует базис. Для приведения булевой функции к виду содержащему лишь связки из базиса S1 могут быть полезны следующие эквивалентности: x  у  x y, x y  (x  y)(x  y) , x  y  xy  xy , x y  x  y, x  y  x &y . 16 2. Система S2={,&} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S1 а затем использовать соотношение 3. x y  xy. Система S3={,} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S1 а затем использовать соотношение 4. xy  x  y. Система S4={1,&,} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S1 а затем использовать соотношения 5. x  1 x , x y  xyxy. Система S5={} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S2 а затем использовать соотношения xy  x y, x  x x . 6. Система S6={} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S3 а затем использовать соотношения x  y  x  y , x  x  x . 7. Система S7={,0} образует базис. Пример 1.7.1. Записать функцию x(yz) в базисе S1={,,}. x  ( y  z)  (x  y  z)  (x  ( y  z))  (x  y  z  y  z)  (x  y  z  y  z) . Пример 1.7.2. Используя теорему Поста проверить, является ли полной система функций S={f1,f2}, где f1  x  y; f 2  x  y. Решение: Проверим какими свойствами обладают данные функции. 1. Сохранимость константы 0. f1(0,0)=0  1=0 – сохраняет константу 0. f2(0,0)= 0  0  1  1  1 – не сохраняет константу 0. 2. Сохранимость константы 1. 17 f1(1,1)=1  0=0 – не сохраняет константу 1. f2(1,1)=0  0=1 – сохраняет константу 1. 3. Самодвойственность. f1 ( x, y)  x  y  x  y  x  y  f1 ( x, y)  x  y – не самодвойственная. Составим таблицы истинности для функций: f 2 ( x, y)  x  y  x  y, и f 2 ( x, y)  x  y. X Y XY X Y X Y X Y 0 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 Из таблицы истинности видно, что f 2 ( x, y)  x  y  f 2 ( x, y)  x  y т.е. f2 - не самодвойственна. 4. Линейность. Построим полином Жегалкина для функции f2 методом неопределенных коэффициентов. P(x,y) имеет вид: P( x, y)  c0  c1  c2 y  c3 xy. Используя таблицу истинности для f2, полученную в п.3, имеем P(0,0)=C0=1  C0=1 P(0,1)=C0  C2=0  1  C2=0  C2=1 P(1,0)=C0  C1=1  1  C1=1  C1=0 P(1,1)=C0  C1  C2  C3=1  1  0  1  C3=1  C3=1. Итак, f2=1  y  xy – не линейна. 5. Монотонность. Очевидно, что наборы упорядочены следующим образом: (0,0)(0,1); (0,0)(1,0); (0,0)(1,1); (0,1)(1,1); (1,0)(1,1). Проверим на монотонность функцию f1: 18 f1(0,0)=0  1=0  f1(0,1)=0  0=0; f1(0,0)=0  f1(1,0)=1  1=1; f1(0,0)=0  f1(1,1)=1  0=0; f1(0,1)=0  0=0  f1(1,1)=1  0=0; f(1,0)=1  1=1  f1(1,1)=1  0=0. Итак, мы получили, что для (1,0)(1,1), не выполняется f1(1,0)f1(1,1), следовательно функция f1–не монотонна. Проверим на монотонность функцию f2(0,0)=1; f2(0,1)=0. Итак, для (0,0)(0,1) мы не получили что f2(0,0)f2(0,1). Следовательно, функция f2–не монотонна. Сведем наши вычисления в таблицу. Функция Не Не Не Не Не сохр.0 Сохр.1 Самодв. Линейность Монотонность * * * * * * f1 f2 * *  Из теоремы Поста, заключаем, что система S  x  y, x  y  – полная. 19 Глава II. Булева алгебра Множество всех булевых в базисе S1={, &, } образуют булеву алгебру. Таким образом в булевой алгебре все формулы записываются при помощи трех связок: , &, . Частично свойства этой алгебры мы рассмотрели в главе I (см., например, основные эквивалентности). В этой главе рассматриваются свойства, специфичные для булевой алгебры и поэтому везде в этой главе мы будем иметь дело только с тремя функциями: , &, . §2.1. Нормальные формы Нормальные формы являются синтаксически однозначным способом записи формулы, реализующей заданную функцию. Если х - логическая переменная, а σ{0,1} то выражение x x   x если   1 если   0 1 если x   x   , 0 если x   или называется литерой. Литеры x и x называются контрарными. Конъюнктом называется конъюнкция литер. Дизъюнктом называется дизъюнкция литер. Например, формулы x yz и x yxx являются конъюнктами, формулы x  y  z и x  y  x - дизъюнктами, а формула z  x является одновременно и конъюнктом и дизъюнктом. Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция конечного числа конъюнктов. Конъюнктивной нормальной формой (КНФ) называется конъюнкция конечного числа дизъюнктов. Более просто: ДНФ - это сумма произведений, а КНФ - это произведение логических сумм Примеры. 20 1. xyyzx ― это ДНФ (сумма произведений). 2. (x  y  z)  (x  y)  z ―это КНФ (произведение сумм). 3. x  y  z  w ― это ДНФ и КНФ (одновременно). 4. x  y  z  w ― это ДНФ и КНФ (одновременно). 5. (xxy)·(yzx)·z ― это КНФ. 6. x  y  z и x  y  x  x ― это ДНФ. 7. x  (x  yz)  x  y  z ― это не нормальная форма (не ДНФ и не КНФ). Пусть функция f записана в базисе S1. Данная функция приводится к нормальной форме следующим путем: 1) используем законы де Моргана, чтобы преобразовать формулу к виду, в котором знаки отрицания относятся только к отдельным переменным; 2) применяем правило снятия двойного отрицания: x=x; 3) далее использовать законы дистрибутивности, причем необходимо использовать первый закон дистрибутивности для приведения к ДНФ H1&(H2H3)=(H1&H2)(H1&H3) , и второй закон дистрибутивности для приведения к КНФ. H1(H2&H3)=(H1H2)&(H1H3). Любая булева функция может иметь бесконечно много представлений в виде ДНФ и КНФ. Например, используя дополнительно законы инверсий и правила операций с константами можно добиться, чтобы в каждом отдельном конъюнкте или дизъюнкте любая переменная входила бы не более одного раза (либо сама либо ее отрицание). Пример 2.1.1. Для приведения к ДНФ используем 1-ый закон дистрибутивности. x  y  x  y  z  (y  z)  x  y  (x  y  z)  (y  z)  (x  y  x  x  y  y  x  y  z)  (y  z)  -это КНФ  (0  x  y  x  y  z)  ( y  z)  (x  y  x  y  z)  ( y  z)  -это другая КНФ 21  x  y у  x  yz y  x  yz  x  yzz  0 0 x yz  x  yz   x  y  z  x  y  z -это ДНФ Пример 2.1.2. Для приведения к КНФ необходимо использовать второй закон дистрибутивности. x  y  x  y  z  x  y  ( x  y  z )  x  y  ( x  y)  z   x  y  z  (x  y)  (x  y  z)  (x  x  y)  (x  y)  (x  z)  (1  y)   ( x  y)  ( x  z) это КНФ §2.2. Совершенные нормальные формы Если в каждом члене нормальной формы представлены все переменные (либо сами, либо их отрицания), причем в каждом отдельном конъюнкте или дизъюнкте любая переменная входит ровно один раз (либо сама либо ее отрицание), то эта форма называется совершенной нормальной формой (СДНФ или СКНФ). Примеры: Пусть задана функция трех переменных f(x,y,z). 1. x  y  z  x  y  z  x  y  z  это совершенная ДНФ. 2. (x  y  z)  (x  y  z)  (x  y  z)  это совершенная КНФ. 3. ( x  y)  ( x  z)  это не совершенная КНФ, т.к. например, в первую сумму не входит переменная z. 4. xyz  это совершенная ДНФ. Теорема 2.2.1. 1. Любая булева функция, не являющаяся тождественным нулем, имеет только одну СДНФ, с точностью до расположения членов. 2. Любая булева функция, не являющаяся тождественной 1, имеет только одну СКНФ, с точностью до расположения членов. 22 Доказательство теоремы проведем конструктивно, как решение следующей задачи: по данной таблице истинности построить СДНФ. Решение рассмотрим на примере функции f(x,y,z) заданной таблично (таб.2.2) при n=3. Пример 2.2.1. По данной таблице истинности (таб.2.2) построить СДНФ. Решение. Таблица 2.2 основные x y z x yz 1 xyz 1 1 xyz 1 1 1 xyz 1 xyz 1 1 xyz 1 1 1 xyz 1 1 1 1 xyz 1 конъюнкции f(x,y,z) Основные конъюнкции (или конституенты_1), включенные в таблицу, соответствуют конкретному набору нулей и единиц, которые принимают переменные x, y, z. Строятся конституенты_1 по следующему правилу: переменная входит в произведение сама, если на данном наборе она принимает значение 1, в противном случае в произведение входит ее отрицание. Так, например, на наборе (0,0,1) переменные x,y принимают значение 0 и поэтому в произведение входят их отрицания, а переменная z принимает значение 1 и поэтому входит в произведение сама. Для данного набора (0,0,1) конституента_1 равна x  y  z . Очевидно, что конъюнкция x  y  z равна 1 только на наборе (0,0,0), а x  y  z равна 1 на наборе (0,0,1) и т.д. (см. по таблице). Далее, заметим, что 23 дизъюнкция двух основных конъюнкций равна 1 ровно на двух наборах, которые соответствуют данным основным конъюнкциям. Например, функция x  y  z  x  y  z равна 1 только на двух наборах – (0,0,0) и (0,0,1), а на всех других наборах она равна 0. Аналогично, дизъюнкция трех основных конъюнкций равна 1 ровно на трех наборах, которые соответствуют данным основным конъюнкциям и т.д. Т.о. получаем правило: для построения СДНФ следует выбрать строки, в которых функция равна 1, а затем взять дизъюнкцию соответствующих основных конъюнкций, получим искомую СДНФ. Так для нашего примера, имеем x  yz  x  y z  x  yz  x  y z  x yz . Задача. По данной таблице истинности построить СКНФ. Конституента_0 для набора нулей и единиц (которые принимают переменные x, y, z) строится следующим образом: переменная входит в дизъюнкцию сама, если на данном наборе она принимает значение 0, в противном случае в произведение входит ее отрицание. Правило для построения СКНФ: следует выбрать строки, в которых функция равна 0, а затем взять конъюнкцию соответствующих конституент_0. В результате получится искомая СКНФ. Так для нашего примера, имеем f  (x  y  z)  (x  y  z)  (x  y  z) . Замечание. Для построения совершенной КНФ функции f, достаточно построить совершенную ДНФ для функции f , а затем использовать f  f и законы де Моргана. Построим СКНФ для нашего примера на основании замечания. 1. Строим СДНФ для отрицания. x yz  x yz  x yz 2. Используем законы де Моргана f  f  x yz  x yz  x yz  x yz & x yz &x yz  24  (x  y  z)  (x  y  z)  (x  y  z) . Описанный способ нахождения СДНФ (и СКНФ) по таблице истинности бывает часто более трудоемким, чем следующий алгоритм. 1. Для нахождения СДНФ данную формулу приводим сначала к ДНФ. 2. Если в некоторый конъюнкт К (т.е. К это произведение некоторого числа переменных или их отрицаний) не входит скажем переменная у, то этот конъюнкт заменяем на эквивалентную формулу K & ( y  y) и, применяя закон дистрибутивности, приводим полученную формулу к ДНФ; если недостающих переменных несколько, то для каждой из них к конъюнкту добавляем соответствующую формулу вида ( y  y) . 3. Если в полученной ДНФ имеется несколько одинаковых конституент единицы, то оставляем только одну из них. В результате получается СДНФ. Замечание: Для построения СКНФ в дизъюнкт не содержащий скажем переменную у добавляем формулу вида y  y , т.е. этот дизъюнкт заменяем на эквивалентную формулу D  y  y и, применяя 2-й закон дистрибутивности. Пример 2.2.2. Построить СДНФ для функции f при помощи эквивалентных преобразований. f  x  y  z  x  ( y  y)  (z  z)  y  z  ( x  x)   x yz  x yz  x yz  x yz  yzx  yzx   x yz  x yz  x yz  x yz  yzx  Отступление: Вычисление СДНФ имеет не только теоретическое, но и большое практическое значение. Например, во многих современных программах с графическим интерфейсом для составления сложных логических условий используется записываются условия, наглядный причем бланк в виде таблицы: в клетках клетки одного столбца считаются 25 соединенными конъюнкцией, а столбцы — дизъюнкцией, то есть образуют ДНФ (или наоборот, в таком случае получается КНФ). В частности, так устроен графический интерфейс QBE (Query-by-Example), применяемый для формулировки логических условий при запросе к СУБД. §2.3. Минимизация ДНФ методом Квайна Каждая формула имеет конечное число вхождений переменных. Под вхождением переменной понимается место, которое переменная занимает в формуле. Задача заключается в том, чтобы для данной булевой функции f найти ДНФ, представляющую эту функцию и имеющую наименьшее число вхождений переменных. Если х - логическая переменная, а σ{0,1} то выражение x x   x если   1 если   0 . называется литерой. Конъюнктом называется конъюнкция литер. Например, формулы x yz и x yxx являются конъюнктами. Элементарным произведением называется конъюнкт, в который любая переменная входит не более одного раза (либо сама либо ее отрицание). Формула f1 называется импликантой формулы f, если f1 — элементарное произведение и f1f=f1, т. е. для соответствующих формулам функций справедливо неравенство f1f. Импликанта f1 формулы f называется простой, если после отбрасывания любой литеры из f1 не получается формула, являющаяся импликантой формулы f. Пример 2.3.1. Найдем все импликанты и простые импликанты для формулы f=xy. Всего имеется 8 элементарных произведений с переменными х и у. Ниже, для наглядности, приведены их таблицы истинности: 26 x y xy xy xy xy xy x y x y 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Из таблиц истинности заключаем, что формулы x  y , x  y , x  y , x ,y— все импликанты формулы xy, а из этих импликант простыми являются формулы x и у (формула x  y , например, не является простой импликантой, поскольку, отбрасывая литеру y , получаем импликанту x ). Сокращенной ДНФ называется дизъюнкция всех простых импликант данной формулы (функции). Теорема 2.3.1. Любая булева функция, не являющаяся константой 0, представима в виде сокращенной ДНФ. В примере 2.3.1 функция, соответствующая формулe xy представима формулой x  y которая является ее сокращенной ДНФ. Сокращенная ДНФ может содержать лишние импликанты, удаление которых не меняет таблицы истинности. Если из сокращенной ДНФ удалить все лишние импликанты, то получается ДНФ, называемая тупиковой. Заметим, что представление функции в виде тупиковой ДНФ в общем случае неоднозначно. Выбор из всех тупиковых форм, формы с наименьшим числом вхождений переменных дает минимальную ДНФ {МДНФ). Рассмотрим метод Квайна, для нахождения МДНФ, представляющей данную булеву функцию. Определим следующие три операции: 1. операция полного склеивания: f  x  f  x  f  (x  x)  f ; 2. операция неполного склеивания: f  x  f  x  f  (x  x)  f  x  f  x  f  f  x  f  x ; 27  3. операция элементарного поглощения: f  x  f  f ,   {0,1} . Теорема 2.3.2 (теорема Квайна). Если исходя из СДНФ функции произвести все возможные операции неполного склеивания, а затем элементарного поглощения, то в результате получится сокращенная ДНФ, т. е. дизъюнкция всех простых импликант. Пример 2.3.2. Пусть функция f(x,y,z) f  x yz  x yz  x yz  x yz  x yz задана совершенной ДНФ . Тогда, производя в два этапа все возможные операции неполного склеивания, а затем элементарного поглощения, имеем f  x  y  ( z  z)  y  z  ( x  x )  y  z  ( x  x )  x  z  ( y  y)  x  y  ( z  z )  x  y  z  x  y  z  x  y  z  x  y  z  x  y  z   x  y  y z  yz  x  z  x  y  x  y  z  x  y  z  x  y  z  x  y  z  x  y  z   y  ( x  x )  y  (z  z )  x  y  y  z  y  z  x  z  x  y  x  y  z  x  y  z  x  y  z  x  y  z  x  y  z   y x  y yz  yz  x z  x  y x  y  z  x  y  z  x  y  z  x  y  z  x  y  z   y xz Таким образом, сокращенной ДНФ функции f является формула yx·z. На практике при выполнении операций неполного склеивания на каждом этапе можно не писать члены, участвующие в этих операциях, а писать только результаты всевозможных полных склеиваний и конъюнкты, не участвующие ни в одном склеивании. Пример 2.3.3. Пусть функция f{x,y,z) задана совершенной ДНФ f  x yz  x yz  x yz  x yz . 28 Тогда, производя операции склеивания, а затем элементарного поглощения, имеем f  x  y  (z  z)  y  z  (x  x)  x  z  ( y  y)  x  y  y  z  x  z Для получения минимальной ДНФ из сокращенной ДНФ используется матрица Квайна, которая строится следующим образом. В заголовках столбцов таблицы записываются конституенты единицы совершенной ДНФ, а в заголовках строк — простые импликанты из полученной сокращенной ДНФ. В таблице звездочками отмечаются те пересечения строк и столбцов, для которых конъюнкт, стоящий в заголовке строки, входит в конституенту единицы, являющейся заголовком столбца. Для примера 2.3.3. матрица Квайна имеет вид импликанты x yz xyz xy * * yz * xz xyz x yz * * * В тупиковую ДНФ выбирается минимальное число простых импликант, дизъюнкция которых сохраняет все конституенты единицы, т. е. каждый столбец матрицы Квайна содержит звездочку, стоящую на пересечении со строкой, соответствующей одной из выбранных импликант. В качестве минимальной ДНФ выбирается тупиковая, которая имеет наименьшее число вхождений переменных. В примере 2.3.3 по матрице Квайна находим, что минимальная ДНФ заданной функции есть x  y  x  z . Замечание. Для построения минимальной КНФ функции f, достаточно построить минимальную ДНФ для функции f , а затем использовать f  f и законы де Моргана. 29 § 2.4. Карты Карно Другой способ получения простых импликант формул с малым числом переменных (и, значит, нахождения минимальной ДНФ) основан на использовании так называемых карт Карно. Карта Карно - это специального вида таблица, которая позволяет упростить процесс поиска минимальных форм и успешно применяется, когда число переменных не превосходит шести. Карты Карно для функций, зависящих от n переменных, представляет собой прямоугольник, разделенный на 2n клеток. Каждой клетке диаграммы ставится в соответствие двоичный nмерный набор. Значения заданной функции f из таблицы истинности вносятся в нужные квадраты, однако если клетке соответствует 0, то обычно она остается пустой. В таб.2.4.1. показан пример разметки карты Карно для функции, зависящей от трех переменных. Нижние четыре клетки карты соответствуют двоичным наборам, в которых переменная x принимает значение 1, четыре верхние клетки соответствуют наборам, в которых переменная x принимает значение 0. Четырем клеткам составляющим правую половину карты, соответствуют наборы, в которых переменная y; принимает значение 1 и т.д. В таб.2.4.2. приведена разметка карты Карно для n=4 переменных. таблица 2.4.1. 30 таблица 2.4.2. Для построения минимальной ДНФ производится процедура склеивания "1". Склеивающимся значениям "1" соответствуют соседние клетки, т.е. клетки отличающиеся лишь значением одной переменной (на графическом изображении разделенных вертикальной или горизонтальной линией с учетом соседства противоположных крайних клеток). Процесс склеивания "1" сводится к объединению в группы единичных клеток карты Карно, при этом необходимо выполнять следующие правила; 1. Количество клеток, входящих в одну группу, должно выражаться числом кратным 2, т.е. 2m где m=0,1,2,... 2. Каждая клетка, входящая в группу из 2m клеток, должна иметь m соседних в группе. 3. Каждая клетка должна входить хотя бы в одну группу. 4. В каждую группу должно входить максимальное число клеток, т.е. ни одна группа не должна содержаться в другой группе. 5. Число групп должно быть минимальным. Считывание функции f по группе склеивания производится следующим образом: переменные, которые сохраняют одинаковые значения в клетках группы склеивания, входят в конъюнкцию, причем значениям 1 соответствуют сами переменные, а значениям 0 их отрицания. Приведем шаблоны, которые помогают строить покрытия 1 (переменные считаем теми же, но их писать не будем). Для упрощения записи мы не будем 31 отмечать переменные, хотя сохраним их обозначения как и в таблицах 2.4.1, 2.4.2. Приведем шаблоны для n=3, которые помогают строить покрытия единицы (1). Приведем шаблоны для n=4, которые помогают строить покрытия единицы (1). 32 Пример 2.4.1. С помощью Карт Карно, построить МДНФ и МКНФ функций заданных вектором своих значений. 1) f(x,y,z)=(1011 0101); 2) f(x1,x2,x3,x4)=(1011 1111 1011 1100). Решение. 1) Занесем данные в карту Карно. Удобно сначала отметить клетки, где функция равна нулю. Функция f равна нулю на наборах, являющимся двоичными разложениями чисел 1,4,6 (т.к. отсчет начинается с 0). Таким образом, f(0,0,1)=f(1,0,0)=f(1,1,0)=0. 33 f  xz  x y  x z − min ДНФ. Для построения МКНФ, построим МДНФ для функции f : f  x z  x yz − min ДНФ f . Переходя к функции f, получим: f  f  x z  x y z  ( x  z )( x  y  z ) – min КНФ. 2) Заносим данные в карту Карно. Получаем, что f(0,0,0,1)=f(1,0,0,1)=f(1,1,1,0)=f(1,1,1,1)=0. Далее, Сначала смотрим, есть ли покрытия_1 из 16 клеток покрывающих хотя бы одну непокрытую 1. Таких покрытий нет. Переходим к покрытиям из 8 клеток. Смотрим, есть ли покрытия 1 из 8 клеток покрывающих хотя бы одну непокрытую 1. Таких покрытий нет. Переходим к покрытиям из 4 клеток. Смотрим, есть ли покрытия 1 из 4 клеток покрывающих хотя бы одну непокрытую 1. Таких покрытий четыре. Таким образом, все 1 стали покрытыми. Далее, смотрим можно ли убрать некоторые покрытия, так чтобы все единицы остались покрытыми. Убрать некоторые покрытия нельзя. Производим считывание функции: f  x2 x3  x1 x3  x3 x4  x2 x3 – МДНФ. 34 Для построения МКНФ Функции f, построим сначала МДНФ, функции f : f  x1 x2 x3  x2 x3 x4 – min ДНФ f . Переходя к функции f, получим:: f  f  x1 x2 x3  x2  x3  x4  ( x1  x2  x3 )(x2  x3  x4 ) – min КНФ. Замечание. Для построения минимальной КНФ функции f, достаточно построить минимальную ДНФ для функции f , а затем использовать f  f и законы де Моргана. Глава III. Алгебра Жегалкина Множество булевых функций, заданный в базисе Жегалкина S4={,&,1} называется алгеброй Жегалкина. Основные свойства. 1. .коммутативность H1H2=H2H1, H1&H2=H2&H1; 2. ассоциативность H1(H2H3)=(H1H2)H3, H1&(H2&H3)=(H1&H2)&H3; 3. дистрибутивность H1&(H2H3)=(H1&H2)(H1&H3); 4. свойства констант H&1=H, H&0=0, H0=H; 5. HH=0, H&H=H. Утверждение 3.1.1. Через операции алгебры Жегалкина можно выразить все другие булевы функции: 35 x=1x, xy=xyxy, xy=1xy, xy=1xxy, xy=1xyxy, xy=1xy. Определение. Полиномом Жегалкина (полиномом по модулю 2) от n переменных x1,x2,…,xn называется выражение вида c0с1x1c2x2…cnxnc12x1x2…c12…nx1x2…xn, где постоянные ск могут принимать значения 0 ли 1. Если полином Жегалкина не содержит произведений отдельных переменных, то он называется линейным ( линей ная функция). Например, f=xyzxyz и f1=1xyz–полиномы, причем второй является линейной функцией. Теорема (Жегалкина). Каждая булева функция представляется в виде полинома Жегалкина единственным образом. Приведем основные методы построения полиномов Жегалкина от заданной функции. 1. Метод неопределенных коэффициентов. Пусть P(x1,x2,…,xn) - искомый полином Жегалкина, реализующий заданную функцию f(x1,x2,…,xn). Запишем его в виде P= c0с1x1c2x2…cnxnc12x1x2…c12…nx1x2…xn. Найдем коэффициенты ск. Для этого последовательно придадим переменным x1,x2,…,xn значения из каждой строки таблицы истинности. В итоге получим систему из 2n уравнений с 2n неизвестными, имеющую единственное решение. Решив ее, находим коэффициенты полинома P(x1,x2,…,xn). 2. Метод, основанный на преобразовании формул над множеством связок {, &}. Строят некоторую формулу Ф над множеством связок{,&}, реализующую данную функцию f(x1,x2,…,xn). Затем заменяют всюду подформулы вида A на A1, раскрывают скобки, пользуясь дистрибутивным законом (см. свойство 3), а затем применяют свойства 4 и 5. 36 Пример 3.1.1. Построить полином Жегалкина функции f(x,y)=xy. Решение. 1. (метод неопределенных коэффициентов). Запишем искомый полином в виде P= c0с1xc2yc12xy Пользуясь таблицей истинности x 1 1 y 1 1 xy 1 1 1 получаем, что f(0,0)=P(0,0)= c0=1, f(0,1)=P(0,1)= c0 c2=1, f(1,0)=P(1,0)= c0 c1=0, f(1,1)=P(1,1)= c0с1c2c12=1 Откуда последовательно находим, c0=1, с1=1, c2=0, c12=1. Следовательно xy=1xxy (сравните с утверждением 3.1). 2.(Метод преобразования формул.) Имеем x  y  x  y  x  y  (x  ( y  1))  1  1  x  x  y . Заметим, что преимущество алгебры Жегалкина (по сравнению с другими алгебрами) состоит в арифметизации логики, что позволяет выполнять преобразования булевых функций довольно просто. Ее недостатком по сравнению с булевой алгеброй является громоздкость формул. 37 Глава IV. Высказывания. Предикаты §4.1. Высказывания При построении алгебры логики мы использовали функциональный подход. Однако, можно было бы построить эту алгебру конструктивно. Сначала определить объекты изучения (высказывания), ввести операции над этими объектами и изучить их свойства. Дадим формальные определения. Высказыванием назовем повествовательное предложение относительно которого можно однозначно сказать истинно оно (значение И или 1) или ложно (значение Л или 0) в конкретный момент времени. Например, «5-простое число», «нажата клавиша «Esc»» и т.д. При помощи связок «не», «и», «или», «если,… то», «если и только если» (им отвечают операции «», «&», «», «», «» соответственно) можно построить более сложные высказывания (предложения). Так строится алгебра высказываний. Для упрощения записи сложных высказываний вводится старшинство связок: «», «&», «», «», «», что помогает опустить лишние скобки. Простые высказывания назовем пропозициональными переменными. Введем понятие формулы. 1. Пропозициональные переменные являются формулами. 2. Если А, В формулы, то выражения А, АВ, АВ, АВ, АВ являются формулами. 3. Формулами являются только выражения, построенные в соответствии с пунктами 1 и 2. Формула, принимающая значение И при всех значениях пропозициональных переменных называется тавтологией (тождественно истинной формулой, общезначимой формулой), а формула, принимающая значение Л при всех значениях пропозициональных переменных называется 38 противоречием (или невыполнимой). Если формула не является общезначимой и невыполнимой, то она называется нейтральной. Описание свойств алгебры высказываний аналогично описанию соответствующих функций в булевой алгебре и мы их опускаем. Пример. После обсуждения состава участников предполагаемой экспедиции было решено, что должны выполняться два условия: а) если поедет Арбузов, то должны поехать еще Брюквин или Вишневский; б) если поедут Арбузов и Вишневский, то поедет и Брюквин. Требуется установить, кто из перечисленных сотрудников войдет в состав экспедиции. Решение. Назначение в экспедицию Арбузова, Брюквина и Вишневского будем обозначать буквами А, Б, В соответственно. Тогда условие а) можно записать в виде АБВ, а условие б) в виде А&В Б. Так как оба условия должны выполняться одновременно, то они должны быть соединены логической связью «и» (конъюнкция равна 1 только в одном случае, когда все переменные равны 1). Поэтому принятое решение можно записать в виде формулы L=(АБВ)&(А&ВБ) эта формула должна быть истинной. Следовательно, для решения задачи можно построить таблицу истинности формулы L и найти значение пропозициональных переменных А,Б,В на которых формула L равна 1. А можно построить СДНФ или СКНФ и естественным образом сделать заключение. Однако, далее применим искусственный подход, с целью записать компактный ответ к задаче. Подвергнем формулу L равносильным преобразованиям, получим: L=( А БB)&( A & B В)=( А БB)&( А  В Б). Применяя к последнему выражению второй закон дистрибутивности, получим L= А [(БВ)&(Б В )] = А [Б(B& В )] = А Б=AБ. 39 Отсюда следует, что если поедет в экспедицию Арбузов, то с ним должен ехать и Брюквин. §4.2. Предикаты. Логические операции над предикатами Предикат (лат. praedicatum – сказанное) – то, что высказывается в суждении об объекте. Предикат отображает наличие того или иного признака у предмета. Другими словами, предикаты — отображения произвольных множеств во множество высказываний. Определение 4.1 Пусть x1,x2,…,xn — символы переменных произвольной природы. Эти переменные будем называть предметными. Пусть наборы переменных (x1,x2,…,xn) принадлежат множеству M=(M1,M2,…Mn), которое будем называть предметной областью (т.е. xiMi, где Мi называются областью определения переменной хi). Предикатом местности n (n-местным предикатом), определенным на предметной области M, называют логическую функцию принимающую либо значение И либо значение Л. Пример 4.2.1. D(x1,x2) = «Натуральное число х1 делится (без остатка) на натуральное число х2» — двуместный предикат, определенный на множестве пар натуральных чисел M=N  N. Очевидно, D(4,2) = И, D(3,5) = 0. Пример 4.2.2. Q(x) ==«x2<-1, хR» — одноместный предикат, определенный на множестве действительных чисел М=R. Ясно, что Q(-1) = Л, Q(5) = Л, и вообще предикат Q(x) — тождественно ложен, т. е. Q(x) = Л для всех хR. Пример 4.2.3. В(x,у,z) =«х2+y2