Конспект лекций Губарь (Конспект лекций "Начальный курс информатики" А.М.Губарь), страница 11

Основные логические операцииСравнительно просто определить, является истинным или ложнымпростое высказывание: для этого достаточно руководствоваться здравымсмыслом и учитывать конкретную ситуацию. Ведь тот факт, что данноевысказывание является истинным или ложным, в общем случае неопределяется самим высказыванием, а зависит от ситуации. Например,высказывание «Меня зовут Саша» будет истинным, если его произноситчеловек с таким именем, и ложным в противном случае. Впрочем,существуют и высказывания, которые являются истинными (или ложными)во всех возможных ситуациях. Такие высказывания называются абсолютноистинными (или абсолютно ложными). Примером первого из них являетсявысказывание «Казимир Малевич написал картину «Черный квадрат»»,примером второго – «Казимир Малевич написал картину «Три богатыря»».Итак, простые (как и составные) высказывания могут принимать толькоодно из двух возможных значений – «истина» или «ложь», которые могутобозначаться как И или Л, true или false, 1 или 0 соответственно.

В алгебрелогики не рассматривается зависимость истинности высказывания отситуации, а изучается лишь, как зависит значение истинности составноговысказывания от значений входящих в него простых высказываний. При этомлогические связки рассматриваются как операции на множестве из двухзначений 0 и 1, то есть {0,1}.И все-таки, как быть с составными высказываниями? Например, какоценить истинность высказывания «Или я – студент, или у меня две головы»,если рассматривать его как одно целое? Для этого необходимоизучитьлогические операции, каждая из которых задается соответствующей ейтаблицей истинности, и правила их выполнения.Обозначение таких операций соответствует обозначению логическихсвязок, основные из которых мы рассмотрели, а правила их выполнения иоценки истинности или ложности следующие.Сложное высказывание вида P  Q истинно только тогда, когда истинныи Р, и Q одновременно, в остальных случаях оно ложно.Это определение может быть представлено и в табличном виде (таблица3.1).Т а б л и ц а 3.1Таблица истинности конъюнкцииP0011Q0101PQ0001Такая таблица называется таблицей истинности, а соответствующаялогическая операция – конъюнкцией или логическим произведением.Последнее название объясняется тем, что в этой таблице фактическизаписаны правила умножения чисел в двоичной системе.

Другие названияэтой операции приведены ниже.Составное высказывание вида P  Q ложно только тогда, когда ложны иР, и Q, в остальных случаях оно истинно.Соответствующая таблицаистинности (таблица 3.2) выглядит следующим образом:Т а б л и ц а 3.2Таблица истинности дизъюнкцииP0011Q0101PQ0111Эта логическая операция называется дизъюнкцией, другие ее названиятакже приведены ниже.Сложное высказывание вида P → Q ложно только тогда, когда Р истинно,а Q ложно, в остальных случаях оно истинно (таблица 3.3).Т а б л и ц а 3.3Таблица истинности импликацииP0011Q0101P→Q1101Это – импликация. Иногда говорят, что результат импликации ложен,если посылка верна, а утверждение – нет.Последняя таблица истинности может вызвать некоторые трудности дляее понимания, в то время как две предыдущие хорошо согласуются ссодержательным смыслом логических связок.

Поэтому проиллюстрируем ееследующими двумя примерами.Очевидно, что высказывание «Если x делится на 4, то x делится на 2»истинно при любом x. Обозначив простые высказывания «x делится на 4» и«x делится на 2» через P(x) и Q(x) соответственно, получим составноевысказывание P(x) → Q(x), истинное при любом x. При x = 3 имеем P(3) = Q(3)= 0; при x = 2 – P(2) = 0, Q(2) = 1; при x = 4 – P(4) = Q(4) = 1. Таким образом,реализуются все строки таблицы истинности для импликации, в которыхзначение импликации есть 1.Высказывание «Если ведьмы существуют, то все они – брюнетки»является истинным в том случае, если ведьмы не существуют.

Вообще-то«правильность» этого утверждения можно установить, пытаясь выяснить узнакомых брюнеток, не являются ли они ведьмами.Рассмотренные три логическиеоперацииназываютсябинарными,потому что их результат зависит от значений двух переменных, но есть ещёи унарная операция,содержащая одну логическую переменную, исоответствующая ей таблица истинности (таблица 3.4).Т а б л и ц а 3.4Таблица истинности инверсииА01Ā10Это – отрицание, инверсия или операция НЕ. Из таблицы истинностивидно, что если простое высказывание A ложно, то его отрицание – истиннои наоборот.

Кстати, вы, очевидно, уже заметили, что в приведенных таблицахистинности «ЛОЖЬ» обозначается как 0, а «ИСТИНА» – как 1.Необходимо отметить, что n-арная логическая операция содержит nпеременных.Каждая из рассмотренных бинарных операций содержит четыре наборазначений аргументов, поскольку в общем случае с помощью n булевыхпеременных, а их у нас здесь две, можно задать 2n различных наборов ихзначений. Понятно, что четырем наборам значений двух аргументов можносопоставить 24 = 16 разных наборов значений логических операций. Поэтому,вообще говоря, всего существует 16 бинарных логических операций и,соответственно, логических функций, представленных в таблице 3.5, нотолько 10 из них имеют самостоятельное значение, так как существеннозависят от обоих аргументов.

К тому же, кроме введенных, частоиспользуются и другие обозначения логических связок и функций, как и ихназвания, которые мы и приведем. Отметим также, что в общем случае на nаргументах можно задать 22^n логических функций.Т а б л и ц а 3.5Бинарные логические функцииАргументыx y ƒƒƒƒƒƒƒƒƒƒ012345678900000000100100011010001010110011110001001101000110101Функцииƒ1 ƒ11 ƒ11011ƒ1ƒ1234110011011110ƒ151111Функция f0 – константа 0, абсолютная ложь.Функция f1 = x  y = x  y = x∙y = xy – «x и y» – конъюнкция, логическоепроизведение, логическое «и», функция совпадения.Функция f2 = ┐(x → y) = x  y – «неверно, что x влечет y; x, но не y» –отрицание импликации, антиимпликация, запрет y.Функция f3 = x – переменная x.Функция f4 = ┐(y → x) = x  y – «неверно, что y влечет x; не x, но y» –отрицание обратной импликации, обратная антиимпликация, запрет x.Функция f5 = y – переменная y.Функция f6 = x  y = ┐(x ↔ y) – «либо x, либо y; x не эквивалентно y» –сумма по модулю 2, отрицание эквивалентности, неравнозначность,разделительная дизъюнкция.Функция f7 = x  y – «x или y; либо x, либо y; либо (x и y)» – дизъюнкция,логическая сумма, логическое «или», функция разделения.Функция f8 = x y = ┐(x  y) – «ни x, ни y» – стрелка Пирса, отрицаниедизъюнкции, антидизъюнкция, функция Вебба.Функция f9 = x ↔ y = x  y = x ~ y – «x тогда и только тогда, когда y; xэквивалентно y» – эквивалентность, равнозначность.Функция f10 = y – «не y» – переменная y, инверсия от y.Функция f11 = y → x – «y влечет x; если y, то x» – обратная импликация.Функция f12 = x – «не x» – переменная x, инверсия от x.Функция f13 = x → y – «если x, то y; x влечет y; x имплицирует y» –импликация, логическое следование.Функция f14 = x  y = ┐(xy) – «x и y несовместны; неверно, что x и y» –штрих Шеффера, отрицание конъюнкции, антиконъюнкция.Функция f15 – константа 1, абсолютная истина.Рассмотренные бинарные логические операции и соответствующие имфункции позволяют сделать следующие выводы.Две функции (f0 и f15) задают константы 0 и 1, функции f10 и f12 задаютунарные инверсии, наконец, функции f3 и f5 задают унарные переменные.Таким образом, действительно только 10 из имеющихся 16-ти бинарныхлогических функций существенно зависят от обоих аргументов.Возможно, кто-то уже заметил, что каждая из функций имеет свой«антипод» –функцию, значения которой противоположны ей на всехнаборах значений аргументов.

При m + n = 15 для любой функции fmсуществует такая функция fn, что fm = ┐fn.3.3. Оценка составных высказыванийС помощью рассмотренных таблиц истинности можно оценивать, (тоесть определять истинность или ложность) любые сложные высказывания,содержащие эти операции. Для этого сначала надо записать все возможныекомбинации переменных (другими словами, ввести исходные данные), азатем последовательно выполнить действия,содержащиеся в логическойформуле. При этом надо учитывать "старшинство" операций, которыесоответствуют логическим связкам. Первой должна выполняться инверсия,затем – конъюнкция, дизъюнкция, а последней выполняется импликация.Такой порядок выполнения называется естественным, если его необходимонарушить, следует применять скобки.

Например, оценим истинностьсоставного высказывания A → B┐С (таблица 3.6).Т а б л и ц а 3.6Пример оценки составного высказыванияA00001111B00110011C01010101┐С10101010В┐С1011101111111011Сначала заполняются три первых столбца таблицы. Фактически, в нихнадо записать восемь трехразрядных двоичных чисел от нуля до семивключительно. Если с этим все еще возникают проблемы, то можновоспользоваться другим правилом: в первом столбце записываются четыренуля и четыре единицы, во втором столбце нули и единицы чередуются черездва, а в третьем – через один. Очевидно, что в случае четырех переменных,содержащихсявисходнойформуле,потребовалосьбызаполнитьшестнадцать строк таблицы, поскольку 24 = 16, а первый столбец (изчетырех) будет содержать восемь нулей и восемь единиц. Затем последующиестолбцы таблицы заполняются по мере выполнения логических действий.