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

Высказывания и функции на высказываниях

Математическая логика является разделом дискретной математики, в котором, в частности, формальными методами изучаются высказывания. Широкое применение кроме самой математики этот ее раздел получил при анализе и синтезе логических схем входа и выхода данных в компьютерах и других цифровых устройствах, в частности: связи, видео- и фотоаппаратуры и др.

Определение 4.1. Любое предложение, о смысле которого можно сказать, истинно оно или ложно, называется высказыванием.

Таким образом, согласно определению, предложение «Я иду на занятия» является высказыванием, а предложения «который час?», «сколько это стоит?», «куда ведет эта дорога?» высказываниями не являются. В соответствии с этим же определением высказывание может иметь два значения: «истина» либо «ложь» или «да» — «нет».

Высказывания могут принадлежать любой предметной области: математике, технике, экономике, социологии, административному управлению, спорту и т.д. Например, высказывания «3 > 5» и «5 > 3», первое из которых ложно, а второе истинно, принадлежат области математики. Высказывание «Спартак» победит «Динамо» — из области спорта, истинно оно или ложно, определяется совокупностью многих факторов. Высказывание «документ получен» — из области административного управления, истинно оно или ложно, зависит от того, какой документ, когда и кем получен, т.е. также от совокупности многих факторов.

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

Таким образом, все приведенные выше высказывания — первичные, т.е. атомы.

Для того, чтобы перейти от первичных высказываний к формальным методам их изучения вводятся логические переменные, которые могут получать два значения: «истина» или «ложь», в зависимости от тех или иных факторов. При этом, от способов получения значений логических переменных абстрагируются.

Пусть, например, переменные х, - а > 0 и х₂ - а < 1, где а — действительная переменная. Значения логических переменных х,, х₂ истинны или ложны в зависимости от значения а. Так, если а - 3, то х, истинно, а х₂ ложно. Если же а - -2, то х, ложно, а х₂ истинно. Ограничиваясь только указанными значениями логических переменных, можно перейти от более простых к более сложным высказываниям. Для этого на конечном множестве логических переменных х,, х₂, ..., х„, принимающих значения «истина»—«ложь» вводятся различные функции.

Определение 4.3. Функция Р(х_х, х₂, ..., х„) множества логических переменных х,, х₂, ..., х„, принимающая значения только «истина» либо «ложь», называется логической функцией.

Определение 4.4. Логические переменные и функции называются вторичными высказываниями, или молекулами.

Работа с молекулами позволяет исследовать свойства логических функций, выполнять обобщения. А затем, в случае необходимости, возвращаться к первичным высказываниям, т.е. атомарному уровню. Например, высказывание х, = а > 0 истинно только в том случае, когда а принадлежит интервалу (0, °°), а высказывание х₂ = а < 0 принимает значение «истина» только тогда, когда принадлежит интервалу (-°° 0). Таким образом, располагая переменными а, можно поставить вопрос о построении функции У^Г(Х|, х₂), которая принимает значение «истина» тогда и только тогда, когда оба аргумента х,, х₂ истинны безотносительно к их первичному смыслу. Построив такую функцию, можно вернуться к первичным высказываниям (атомарному уровню) и поставить вопрос о таком высказывании, которое бы соответствовало данной функции. В нашем случае оно звучит так: «переменная а принадлежит интервалу [0,1]».

Как и любая функция, всякая логическая функция п переменных может быть задана таблицей. В левой части этой таблицы перечисляются все наборы значений логических переменных, а в правой — значения функции на этих наборах. При этом для сокращения записей «истина»—«ложь» эти слова кодируются числами 1,0.

Таким образом, табличное представление логической функции — это таблица, строки которой состоят из последовательностей нулей и единиц. Пример такой таблицы, задающей функцию трех переменных Г(х_{, х₂, х₃) показан на рис. 4.1.

Следует сказать, что числовые значения таблицы не являются числами в обычно понимаемом смысле. Они не определяют количество и, тем более, не допускают никаких арифметических операций. Они используются лишь для сокращения записей И ЯВЛЯЮТСЯ крат- Рис. 4.1. Табличное пред-чайшим кодом для ввода в ЭВМ, значе- давление логической Функ-

нии «истина»—«ложь». Количество раз- ^{р р}

личных наборов значений логических

переменных, т.е. различных комбинаций нулей и единиц, зависит от числа логических переменных, т.е. количества компонент вектора х,, х₂,..., х_п. В связи с тем, что каждая переменная принимает только два значения, по общему правилу комбинаторики, а именно, правилу произведения, получаем, что общее число комбинаций равно 2". Для каждой комбинации логическая функция Сможет принимать два значения: «истина» либо «ложь». Поэтому по тому же правилу произведения получаем, что общее число значений логической функции У⁷ при длине вектора аргументов п равно 2²'. В зависимости от п это число очень быстро растет. Так, для п - 2 оно равно 16, для /7 = 4— 65 536 и т.д. Поэтому, несмотря на то, что при любом конечном значении п число всех функций У⁷конечно, работа с ними затруднена уже при /7 = 10. В дальнейшем мы рассмотрим преимущественно функции одной х, и двух х,, х₂ переменных, а также некоторые функции трех аргументов.

Любая функция может быть представлена операцией, если все ее значения лежат в области определения этой же функции. В этом смысле все логические функции математической логики могут рассматриваться как операции. На этом основании термины «функция» и «операция», употребляющиеся в тексте, считаются эквивалентными. Кроме этого, табличной форме задания функции часто соотносят термин «таблица истинности», который также будет употребляться в дальнейшем. Наборы значений переменных х_х,х₂, ..., х_п, на которых логическая функция принимает значение 1, т. е. /(х,, х₂ ,..., х_п) = 1, нередко называют единичными наборами функции, а множество единичных наборов — единичным набором F. Соответственно наборы значений переменных х,, х₂, х_п, на которых F = 0, называют нулевыми наборами F.

Переменная х, функции /(х,, ..., х_м, х,, х_/+1,..., х_п) называется несущественной (фиктивной), если /(х,, ..., х_м, 0, х_/+1, ..., х„) = /(х,, ..., x,_j, 1, x_J+1,..., х„)при любых значениях остальных переменных, т. е. если изменение значения х,. в любом наборе значений х,, ..., х_п не меняет значения функции. В этом случае функция /(х,, ..., х_п) по существу зависит от (п - 1)-й переменной и может быть представлена функцией С(х_1? ..., х_м, х_/+1, ..., х_п). Говорят, что функция G получена из функции /’удалением фиктивной переменной, а функция / получена из С введением фиктивной переменной.

Смысл удаления фиктивных переменных очевиден: они просто являются лишними. Однако иногда бывает полезно вводить фиктивные переменные. В частности, число всех логических

функций 2²" справедливо именно для того случая, когда учитываются все функции с фиктивными переменными.

Логических функций одной переменной — четыре. Они приведены в таблице на рис. 4.2.

Функции F₀ и F₃ не зависят от значения х, т. е. х для них фиктивная переменная. Функция /, «повторяет» х, т. е. /₃(х) = х. Функция F₂ называется отрицанием х или функцией

Рис. 4.2. Таблица истинности логической функции одной переменной

«НЕ», обозначается х и читается «не х». Значение ее противоположно значению х. Если значение х = 1, то х = 0 и наоборот. Все логические функции одной переменной называются унарными операциями на множестве кодов {0, 1}.

Логических функций двух переменных (бинарных операций) — шестнадцать. Они приведены в таблице на рис. 4.3.

Рис. 4.3. Таблица истинности логических функций двух переменных

Функции /’о, Р₁₅ не зависят от значений х,, х₂, т. е. х,, х₂ для них фиктивные переменные. Функция Т⁷! называется конъюнкцией х, и х₂ и обозначается х,&х₂ или х, лх₂. Она имеет значение «истина» только в одном случае, когда значения х,, х₂ истинны, т. е. х, = х₂ = 1. Поэтому ее часто называют функцией (операцией) «И». Еще одно ее название — «логическое умножение», поскольку ее таблица истинности совпадает с таблицей умножения чисел 0 и 1. В практических условиях, в частности, при составлении программ для ЭВМ на языках высокого уровня, конъюнкция часто используется, например, в таких выражениях: «если а е X и Ье У, то...».

Рассмотрим высказывание У = х, д х₂, где х, = а е А, х₂ = -аеВиЛ, В — произвольные множества. По определению конъюнкции это высказывание истинно только тогда, когда оба значения х,, х₂ истинны, т. е. х, = 1, х₂ = 1. Но это условие выполняется только в том случае, когда элемент а одновременно принадлежит множествам А, В, т.е. их пересечению АГ В. Иными словами, при интерпретации конъюнкции относительно множеств она эквивалентна пересечению этих множеств. Причем это справедливо для х, дх₂ л ... л х_п = л"_=|х,-. Функция называется дизъюнкцией х, и х₂ и обозначается х, vx₂. Она имеет значение «истина»

в тех случаях, когда хотя бы одна из переменных х,, х₂ истинна или истинны обе переменные. Поэтому ее часто называют операцией «или».

Пусть имеется высказывание у - х, vx₂, где х, - а е А, х₂ = а е В, А, В — произвольные множества. По определению дизъюнкции это высказывание истинно только тогда, когда либо х, = 1 и х₂ = 0, либо х, = 0 и х₂ = 1, либо х, = 1 и х₂ = 1. Но эти условия выполняются в тех случаях, когда элемент а принадлежит либо множеству А, либо множеству В, либо одновременно двум множествам, что равносильно принадлежности а объединению множеств А, 5, т. е. А[]В. Причем это справедливо для

X, = у”₌₁ X,.

Функция Р₆ называется разделительной дизъюнкцией х,, х₂, исключающим «ИЛИ» либо сложением по модулю два. Из таблицы истинности (рис. 4.3) видно, что она принимает значение «истина» в двух случаях: когда один операнд х, или другой операнд х₂ истинны, но не оба вместе. Отсюда происходит название операции «исключающее или». Она имеет обозначение ©. Интерпретация разделительной дизъюнкции относительно множеств состоит в том, что объединение множеств не включает их пересечения.

Функция Т₉ называется эквивалентностью или равнозначностью и обозначается х, ~ х₂. Она имеет значение «истина» только

в тех случаях, когда оба ее аргумента истинны либо ложны. В других случаях эта функция имеет значение «ложь».

Функция Р$ называется стрелкой Пирса и обозначается так: 4.

Она принимает значение «истина» только тогда, когда ее операнды х,, х₂ ложны. По таблице истинности она инверсна функции

Р₇, т.е. противоположна Р₇.

Функцию Р₁ з толкуют как операцию импликации и обозначают так: —к По отношению к доказательствам эта функция соответствует фразе: «если А..., то В...». Такая фраза ложна только в том случае, когда из «истины» следует «ложь», что и показывает таблица истинности этой функции.

Функция Р,₄ — это штрих Шеффера. Она имеет обозначение

х, | х₂ и инверсна функции Р,. Ее истинное значение утверждает, что «кто-то лжет». Функция имеет значение «ложь» только в одном случае, когда оба операнда х,, х₂ истинны.

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

Среди логических функций трех аргументов х₁, х₂, х₃ широко известной является мажоритарная функция, на основе которой в свое время строились комбинационные схемы элементов вычислительной техники. Таблицы истинности мажоритарной функции Р_т и инверсной к ней функции У⁷,,, приведены на

Рис. 4.4. Таблицы истинности мажоритарной /%„ и инверсной Т_т к ней функции трех переменных

рис. 4.4. Мажоритарная функция Р_т задана на восьми наборах (комбинациях) ее аргументов. Она принимает значение «истина» в тех случаях, когда два или три ее аргумента истинны. Иными словами, таблица ее истинности отражает торжество большинства единиц. Отсюда, собственно говоря, и происходит ее название — мажоритарная, т. е. отображающая большинство.