Учебники 80131

ФГБОУ ВО «Воронежский государственный технический университет»

Кафедра высшей математики и физико-математического моделирования

ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

для организации самостоятельной работы по дисциплине «Математика» для студентов направления 11.03.01 «Радиотехника», профиля «Радиотехнические средства передачи, приема и обработки сигналов», специальности 11.05.01 «Радиоэлектронные системы и комплексы», специализации «Радиоэлектронные системы передачи информации», направления 11.03.03 «Конструирование и технология электронных средств», профиля «Проектирование и технология радиоэлектронных средств», направления 12.03.01 «Приборостроение», профиля «Приборостроение» очной формы обучения

Воронеж 2017

дится на берегу реки Волга»; «Царевич Дмитрий был убит по приказу Бориса Годунова». Первое предложение истинно, второе ложно, а третье до сих пор обсуждается историками. Предложения: «y = sin x», «На какую оценку студент Петров хочет сдать коллоквиум?» не являются высказываниями. Также не является высказыванием предложение «Цветы расцветают весной» ввиду недостаточной уточненности.

В логике высказываний интересуются не содержанием высказываний, а их истинностью или ложностью, то есть их истинностным значением. Истинностные значения истина и ложь будем обозначать 1 и 0 соответственно. Множество {0, 1} называется множеством истинностных значений.

Рассмотрим логические операции над высказываниями, при которых истинностные значения составных высказываний определяются только истинностными значениями составляющих высказываний, а не их смыслом.

Отрицанием высказывания Р называется высказывание, которое истинно тогда и только тогда, когда Р ложно. Отрица-

ние высказывания Р обозначается P (или Р) и читается "не Р". Отрицание высказывания определяется первым и третьим столбцами таблицы истинности (табл. 1).

Конъюнкцией двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда истинны оба высказывания.

Конъюнкция высказываний P и Q обозначается P Q, читается "P и Q". Конъюнкция определяется первым, вторым и четвертым столбцами табл. 1.

Дизъюнкцией высказываний P и Q называется высказы-

2

вание, ложное тогда и только тогда, когда оба высказывания ложны.

Дизъюнкция высказываний P и Q обозначается P Q, читается "P или Q". Дизъюнкция определяется первым, вторым и пятым столбцами таблицы истинности 1.

В разговорной речи конъюнкции соответствует соединение высказываний союзом "и", а дизъюнкции - союзом "или" в неразделительном смысле. Союз "или" может быть использован и в разделительном смысле: или только P или только Q (но не вместе). В этом случае будем использовать знак , а выражение P Q будем называть суммой по моду-

лю 2 или разделительной дизъюнкцией. Таблица истинности для этой логической связки представлена первым, вторым и восьмым столбцами табл. 1.

Импликацией двух высказываний P и Q называется высказывание, ложное тогда и только тогда, когда P истинно, а Q ложно.

Импликация высказываний P и Q обозначается через P Q и читается "если P, то Q", "из P следует Q". Высказывание P называется посылкой импликации, высказывание Q - заключением. Импликация определяется первым, вторым и шестым столбцами табл. 1.

Эквиваленцией двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда истинностные значения P и Q совпадают.

Эквиваленция высказываний обозначается P Q и читается "P эквивалентно Q". Эквиваленция определяется первым, вторым и седьмым столбцами табл. 1.

Определим далее понятие формулы логики высказываний. Введем сначала некоторые вспомогательные понятия.

Алфавитом называтся любое непустое множество. Элементы этого множества называются символами данного алфавита. Словом называется произвольная конечная последовательность символов (возможно, пустая). Произведением слов a и b называется слово ab. Слово b называется подсловом слова a, если a = a1 b a2 для некоторых слов a1 и a2. Слово b

3

может входить как подслово в слово a несколько раз. Результатом замены данного вхождения подслова b в слово a1 b a2 на слово с называется слово a1 с a2. Результатом подстановки в слово a вместо символа c слова b называется слово, полученное из а одновременной заменой всех вхождений подслова c на слово b.

Алфавит логики высказываний содержит следующие символы: высказывательные (пропозициональные) переменные (ПП) X1, X2, ...; логические символы , , , , ; символьные скобки ( ). Считается, что приоритет применения логических связок возрастает в следующем порядке: , , ,

, . При необходимости изменить эту последовательность действий используют скобки.

Понятие формулы алгебры высказываний или пропозициональной формулы (ПФ), вводится по индукции:

1) любая пропозициональная переменная – ПФ;

является ПФ, когда она построена в соответствии с 1) или 2). Подформулой формулы А называется любое подмно-

жество А, само являющееся формулой.

Будем далее предполагать, что каждое вхождение знака относится к наикратчайшей подформуле, следующей за

ним.

X3 нет логической связки.

Если каждой ПП, входящей в формулу, придавать истинностные значения 0 и 1, то формула будет определять истинностную функцию, то есть функцию, определенную на множестве {0, 1} со значением в этом же множестве. Истин-

4

ностная функция обычно представляется таблицей истинности.

Пример 2. Построим таблицу истинности для формулы

Упорядоченный набор ПП X1, X2, ... называется списком переменных формулы А, если в этом наборе содержатся все переменные, входящие в А. Если некоторые переменные из списка не входят явно в формулу А, то они называются фиктивными. Так, список переменных в примере 2 может иметь вид X1, X2, X3, X4, X5, но переменные X4, X5 являются фиктивными. Оценкой списка переменных назовем сопоставление каждой переменной списка некоторого истинностного значения. Если список содержит k переменных, то имеется 2k различных оценок, следовательно, таблица истинности этой формулы содержит 2k строк.

5

Заметим, что при любых значениях ПП последняя формула принимает значение истина. Такие формулы называют-

ся тавтологией или тождественно-истинными формулами.

Приведем еще некоторые определения. Формула А называется тождественно-ложной, если при любых значениях ПП она принимает значение ложь.

Формула А называется выполнимой, если при некоторых значениях ПП, входящих в нее, она принимает значение истина.

Формула А называется опровержимой, если при некоторых значениях ПП, входящих в нее, она принимает значение ложь.

Формула ((X1 X2 ) X3 ) X1 , таблица истинности

которой построена в примере 2, является выполнимой и опровержимой, но не является тавтологией или тождественноложной.

2. БУЛЕВЫ ФУНКЦИИ

Булевой функцией f x1, x2 ,..., xn называется функция,

которая принимает два значения 0 или 1 и аргументы которой принимают эти же значения.

Существуют различные способы задания булевой функции. Один из них – таблица, в которой указаны все значения ее аргументов и соответствующие значения функции. Например булева функция двух аргументов может быть задана табл.

4.

Полагая, что истинностному значению истина соответствует число 1, а значению ложь - 0, можно считать, что в столбцах 3–8 табл. 1 указаны значения булевых функций, соответствующие логическим операциям , , , , , . В последнем столбце табл. 2 также содержатся значения буле-

вой функции, соответствующие ПФ ((X1 X2 ) X3 ) X1 .

Таким образом, любая булева функция f (x1, x2, ... xn), тождественно не равная нулю, может быть задана соответствующей

6

ПФ, зависящей от пропозициональных переменных x1, x2, ...

xn. При этом, если формуле F1 соответствует функция f1, а F2 - f2 и F1 = F2, то f1 = f2. Справедливо и обратное утверждение: если f1 = f2, то F1 = F2. В рассмотренных выше примерах по заданным ПФ найдены булевы функции. Задание отыскания ПФ, соответствующей заданной булевой функции, будет рассмотрена в параграфе 6.

Таблица 4

3. РАВНОСИЛЬНЫЕ ФОРМУЛЫ

Пусть А и В – две формулы, зависящие от одних и тех же пропозициональных переменных. Они называются равносильными, если при всех наборах значений переменных принимают одинаковые значения.

Равносильность формул А и В обозначается А В. Теорема. Для любых формул А, В, С справедливы сле-

7)A (B C) (A B) (A C) (дистрибутивность дизъюнкции относительно конъюнкции);

8)A (B C) (A B) (A C) (дистрибутивность конъюнкции относительно дизъюнкции);

7

Доказательство. Любая из приведенных равносильностей легко может быть доказана с помощью таблиц истинности. Построим таблицу истинности, например, для равносильности 12.

Приведем правила, с помощью которых можно переходить от одних равносильностей к другим.

1. Пусть A B и C – произвольная формула. Тогда

А B , A C B C, A C B C, A C B C, C A C B, A C B C.

2. Пусть СА – произвольная формула, содержащая А в

8