Основные связки и таблицы истинности

Каждая научная теория есть система каких-то предложений или высказываний, поэтому их природа бесконечно разнообразна. Исследовать внутренюю структуру отдельного высказывания, также как дать точное опредление высказывания, достаточно трудно. Это скорее вопросы лингвистики, чем математики. Поэтому мы ограничимся интуитивным понятием о том, что можно считать отдельными самостоятельными высказываниями. Один из вопросов, изучаемый математической логикой, - это различные сочетания высказываний. Если из двух или более простых высказываний составить новое предложение, то можно получить так называемое составное высказывание. Те высказывания, из которых оно было образовано, называются его простыми составляющими.

Основное свойство каждого высказывания состоит в том, что высказывание должно быть либо истинно, либо ложно, но не может быть истинным и ложным одновременно. Значение «истина» будем обозначать знаком «1», «ложь» ─ «0».

Заметим, что одно и то же высказывание, например «Сегодня идет дождь», может быть и истинным и ложным в зависимости от обстоятельств. Однако существуют и такие высказывания, которые всегда истинны, или всегда ложны. Для составного высказывания достаточно знать, какие из его компонент истинны – это и будет определять истинность всего высказывания.

Таким образом, мы будем изучать два вопроса:

1) Какими способами может быть составлено составное высказывание;
2) Как определить значение истинности составного высказывания по значениям истинности его компонент.

Введем необходимые нам обозначения. Высказывания мы будем обозначать прописными буквами латинского алфавита Введем необходимые нам обозначения. Высказывания мы будем обозначать буквами латинского алфавита Введем необходимые нам обозначения. Высказывания мы будем обозначать буквами латинского алфавита p,q,r и т.д. Нужны еще и символы операций с ними, т.е. символ отрицания высказывания и символы комбинаций (связок) высказываний. Введем их с помощью примеров. Пусть имеется два простых высказывания: «Сегодня жарко» и «Погода хорошая». Обозначим их p и q соответственно.
Допустим, что мы хотим образовать составное высказывание, утверждающее одновременную правильность обоих предыдущих высказываний: «Погода хорошая и сегодня жарко».

Определение 1. Составное высказывание, утверждающее одновременную истинность двух простых высказываний p и q называется конъюнкцией.

Связку конъюнкции «и p и q одновременно» обозначим pq. 

Теперь рассмотрим более осторожное утверждение о том, что истинно хотя бы одно из двух высказываний: «Сегодня жарко или погода хорошая».

Определение 2 . Составное высказывание, утверждающее, что истинно одновременно хотя бы одно из двух высказываний p или q , называется дизъюнкция. Связку дизъюнкции «или p , или q , или оба сразу» обозначим pq .

И наконец, пусть мы считаем ложным одно из высказываний. Например, мы считаем, что «Сегодня не жарко». Запишем это символически как «не p » или отрицание и обозначим ¬p .

Используя эти три простые связки, мы можем составлять более сложные составные высказывания. Например, ¬pq обозначает высказывание «Сегодня не жарко и погода хорошая».

Истинность составного высказывания определяется значениями истинности его компонент. Установим, каким образом истинность каждой из введённых нами связок зависит от истинности составляющих ее простейших высказываний. Очень удобно изображать эту зависимость с помощью таблиц истинности. Для каждой связки может быть определена своя таблица. Для удобства мы их объединили в одну таблицу:

Таблица 1.Ассоциативная связь

Каждое из двух отдельных высказываний p и q может быть либо истинным, либо ложным. Следовательно, возможны четыре пары значений истинности для двух высказываний одновременно. В первых двух столбцах приведены все возможные сочетания пар значений для

p и q . Третий столбец представляет таблицу истинности для отрицания высказывания.
Рассмотрим составное высказывание конъюнкции pq . Ответ на вопрос, в каких случаях истинно это высказывание, получается сразу: если p и q оба истинны, то и их конъюнкция истинна, в противном случае она ложна. В приведенной ниже таблице четвертый столбец представляет таблицу истинности конъюнкции.
Обратимся теперь к составному высказыванию pq , дизъюнкции p и q . В нем утверждается, что имеет место истинность того или другого простейшего высказывания. Тем самым довольно просто заполнить те строчки таблицы, когда истинно одно из двух высказываний, или ложны оба одновременно. Остается неопределенным случай, когда истинны оба высказывания одновременно. Действительно, высказывания «Я нахожусь в Новосибирске» и «Я нахожусь в Москве» не могут быть истинными одновременно. Хотя, если высказывания «Я съем пирожок» и «Я съем яблоко» истинны, то ничто не мешает быть им истинными одновременно. Другими словами, в этом случае может быть истинно высказывание . Для того, чтобы отличать эти два вполне корректных употребления связки «или», назовем первое из них дизъюнкцией в исключающем смысле (или то, или другое, но не оба сразу). А второе – дизъюнкцией в неисключающем смысле (одно или другое, или оба сразу). Всюду в дальнейшем, употребляя символ дизъюнкции, будем иметь в виду дизъюнкцию в неисключающем смысле. В итоге получаем таблицу истинности для дизъюнкции, представленную пятым столбцом таблицы.

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

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

Таким образом, мы имеем новую связку, называемую импликацией и обозначаемую pq . Если p истинно, а q ложно, то pq ложно. Первые две строки таблицы заполняются просто. Построение двух остальных несколько сложнее. Действительно, каким может быть значение импликации, если p ложно? Так как нельзя сохранять здесь неопределенность, то мы волевым образом решаем, что импликация истинна всякий раз, когда p ложно, независимо от значения истинности q . Образно говоря, когда p ложно, тогда мы оправдываем импликацию «за недостаточностью улик » и рассматриваем ее как истинную. Таблица истинности импликации представлена шестым столбцом таблицы.
Определим последнюю связку, с которой мы будем работать pq , и которая тесно связана с импликацией – двойную импликацию. Она может быть прочитана как p если и только если q .

Определение 4. Двойная импликация означает, что если p истинно, то и q истинно, а если p ложно, то и q ложно.

Таблица истинности двойной импликации составляется без труда и представлена в последнем столбце нашей таблицы.

Составные высказывания могут включать в себя простейшие связки по несколько раз, подобно тому, как с помощью простейших арифметических операций образуют сложные алгебраические выражения. Их нужно читать «изнутри наружу», подобно арифметическим выражениям. Каждое из составных высказываний имеет свою таблицу истинности, которая может быть построена стандартным методом. Построение таблицы истинности начинаем с того, что в первых двух столбцах выписываем четыре возможных пары значений истинности для высказываний p и q . После этого записываем наше составное высказывание, оставляя место между символами, с тем, чтобы можно было заполнять столбцы под ними. Затем рассматриваем самое внутреннее сочетание высказываний p и q и записываем его значения истинности в соответствующий ему столбец. Таким образом, двигаясь «изнутри наружу» последовательно заполняем все столбцы. Значение истинности составного высказывания получим в последнем столбце, заполненном в итоге всей процедуры.
Например, пусть высказывание p означает «Иванов умен», высказывание q означает «Петров умен». Тогда составное высказывание означает «или Иванов умен, или Петров глуп». Таблица истинности для него, составленная выше описанным способом, представлена ниже. В нижней строке буквами a, b, c обозначена последовательность шагов.

Таблица 2.

Ассоциативная связь

Следует отметить, что изучаемая нами логика – это, как правило, формальная логика. В обычной речи простые высказывания обычно комбинируют тогда, когда между ними существует какая-то связь. Мы можем сказать «Если сегодня я получу стипендию, то пойду в ресторан». Но мы не скажем: «Если погода хорошая, то я получу стипендию». Однако эта связь зависит от точки зрения, и имеет очень неясный характер. Мы не будем предполагать в наших рассмотрениях никакой внутренней связи между комбинируемыми высказываниями. Это свободное употребление импликации приводи иногда к результатам, которые могут показаться странными с точки зрения обыденной речи. Например, в соответствии с шестым столбцом таблицы истинности высказывание «Если 2х2=5, то коровы живут на луне» истинно, тогда как высказывание «Если 2х2=4, то существуют ведьмы» - ложно. Мы могли бы считать такие высказывания бессмысленными. Но следует понимать, что связка импликации не означает никакой причинной связи. Смысл импликации полностью определен таблицей истинности и ничего другого импликация не подразумевает.

Построение высказывания с заданной таблицей истинности

В предыдущем разделе было показано, как строить таблицу истинности для любого составного высказывания, представляющего собой комбинацию простых высказываний. Представляет интерес и ответ на противоположный вопрос: как для заданной таблицы истинности построить высказывание ей соответствующее. Сразу заметим, что таких высказываний может быть несколько и очевидно, что они должны быть составными. Построение таких высказываний не представляет больших трудностей, более того, при этом можно использовать только связки . Для примера такого построения используем составное высказывание с тремя переменными. Сначала построим высказывания, которые будут истинными только для одной из строчек заданной таблицы истинности. Такие высказывания называют основными конъюнкциями. Заметим теперь, что дизъюнкция двух основных конъюнкций будет истинна ровно в двух случаях, дизъюнкция трех основных конъюнкций истинна в трех случаях и т.д. Следовательно, чтобы построить высказывание с заданной таблицей истинности, надо просто взять дизъюнкцию основных конъюнкций из тех строк, которым в заданной таблице истинности соответствует значение истины. Такой метод не обязательно приводит к построению простейшего из возможных высказываний. Однако он имеет такие преимущества, как механический прием построения высказывания и стандартную его форму. Результат построения основных конъюнкций продемонстрирован в таблице 3. Их дизъюнкция дает высказывание a .

Таблица 3.

Ассоциативная связь