Пример 1. Установить истинность высказывания · С
Решение. В состав сложного высказывания входят 3 простых высказывания: А, В, С. В таблице заполняются колонки значениями (0, 1). Указываются все возможные ситуации. Простые высказывания от сложных отделяются двойной вертикальной чертой.
При составлении таблицы надо следить за тем, чтобы не перепутать порядок действий; заполняя столбцы, следует двигаться “изнутри наружу”, т.е. от элементарных формул к более и более сложным; столбец, заполняемый последним, содержит значения исходной формулы.

А	В	С		А+		· С
0	1	1	0	0	1	1

Из таблицы видно, что данное высказывание истинно только в случае, когда А=0, В=1, С=1. Во всех остальных случаях оно ложно.

Эквивалентность высказываний.

С помощью таблиц истинности можно установить эквивалентность двух или нескольких высказываний.

Высказывания называются эквивалентными, если соответствующие значения каждого из них совпадают в таблице истинности.

Пример 2. Утверждается, что высказывание А+В· С эквивалентно высказыванию (А+В)· (А+С)
Решение. Проверка ведется путем составления таблицы истинности.

А	В	С	В С	А+В· С	А+В	А+С	(А+В)· (А+С)

Сравнивая 5-ю и 8-ю колонки убеждаемся, что все значения, получаемые по формуле А+В· С, совпадают со значениями, получаемыми по формуле (А+В)· (А+С), т.е. высказывания эквивалентны (равносильны). Одно может заменить другое.
Эквивалентные (равносильные) высказывания соединяют знаком º А + В·Сº (А+В)· (А+С).
Отметим различие между эквивалентностью и эквиваленцией.
Эквиваленция является логической операцией, позволяющей по двум заданным высказываниям А и В построить новое А« В.
Эквивалентность же является отношением между двумя составными высказываниями, состоящим в том, что их значения истинности всегда одни и те же.

Тавтология.

Пусть дано высказывание А· и необходимо составить таблицу истинности.
Высказывание А· ложно, истинность его не зависит от истинности высказывания А.

Рассмотрим высказывание В+ .
В этом случае высказывание В+ всегда истинно, независимо от истинности В.

В		В+

Высказывания, истинность которых постоянна и не зависит от истинности входящих в них простых высказываний, а определяется только их структурой, называются тождественными или тавтологиями.
Различают тождественно-истинные и тождественно-ложные высказывания.
В формулах каждое тождественно-истинное высказывание заменяется 1, а тождественно-ложное - 0. Закон исключенного третьего.
A· º 0
В+ º 1

Пример 3. Докажите тавтологию (XÙ Y)® (XÚ Y)
Решение.

Т.к. высказывание (XÙ Y)® (XÚ Y) всегда истинно, то оно является тавтологией.

Пример 4. Докажите тавтологию ((X® Y)Ù (Y® Z))® (X® Z)
Решение.
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ F1 _ _ _ _ F2 _ _ _ _ _ F

X	Y	Z	X® Y	Y® Z	X® Z	F1Ù F2	(F1Ù F2) ® F3

Из таблицы видно, что исследуемое высказывание - тавтология, т.к. оно истинно постоянно.

Вопросы и задания.

1. Какому из ниже приведенных высказываний:

а) (A+C); б) +B; в) +C); г) A+ ;
эквивалентно высказывание (B+C)

2. Установите с помощью таблиц истинности, какие из следующих формул - тавтологии:
а) « ); б) ; в) ;

г) ; д) (X® Y)« (Y® X); е) (X® Y)« ;

ж) (X® Y)« .

3. Установить истинность высказывания

4. Эквивалентны ли высказывания:
и ?

5. Установить, является ли данное высказывание тавтологией:
а) ; б)

6. Для каждой формулы придумайте формализуемые ими предложения:
а) ; б) ; в) .

7. Из простых высказываний: “Виктор хороший пловец” - А; “Виктор хорошо ныряет” - В; “Виктор хорошо поет” - С, составлено сложное высказывание, формула которого имеет вид:
X=(A+C)· (A+B). Установить, эквивалентно ли высказывание Х высказыванию: “Виктор - хороший пловец и Виктор хорошо поет”.

8.
а) ; б) ;
в) ((X1® X2)® X3)Ù (X3« X1); г) ((X® Y)Ù (Y® Z))® (X® Z).

9. Установить истинность высказываний:
а) , , ;
б) , , ;
в) , , ;
г) , , .

Законы логики

Равносильности формул логики высказываний часто называют законами логики.
Знание законов логики позволяет проверять правильность рассуждений и доказательств.
Нарушения этих законов приводят к логическим ошибкам и вытекающим из них противоречиям.
Перечислим наиболее важные из них:
1. Xº X Закон тождества
2. Закон противоречия
3. Закон исключенного третьего
4. Закон двойного отрицания
5. XÙ Xº X , XÚ Xº C Законы идемпотентности
6. C Ù U º U Ù C , C Ú U º U Ú C Законы коммутативности (переместительности)
7 . (C Ù U) Ù Z ºC Ù (U Ù Z) , (C Ú U) Ú Z º C Ú (U Ú Z) - Законы ассоциативности (сочетательности)
8. C Ù (U Ú Z) º (C Ù U) Ú (C Ù Z) , C Ú (U Ù Z) º (C Ú U) Ù (C Ú Z) - Законы дистрибутивности (распределительности)
9. , Законы де Моргана
10. XÙ 1º C , C Ú 0 º C
11. C Ù 0 º 0 , C Ú 1 º 1
12. C Ù (C Ú U) º C , C Ú (C Ù U) º C Законы поглощения
13. (C Ú U) Ù ( Ú U) º U , (C Ù U) Ú ( Ú U) º U Законы склеивания

1-й закон сформулирован древнегреческим философом Аристотелем. Закон тождества утверждает, что мысль, заключенная в некотором высказывании, остается неизменной на протяжении всего рассуждения, в котором это высказывание фигурирует.

Закон противоречия говорит о том, что никакое предложение не может быть истинно одновременно со своим отрицанием.
“Это яблоко спелое” и “Это яблоко не спелое”.

Закон исключенного третьего говорит о том, что для каждого высказывания имеются лишь две возможности: это высказывание либо истинно либо ложно. Третьего не дано. “Сегодня я получу 5 либо не получу”. Истинно либо суждение, либо его отрицание.

Закон двойного отрицания. Отрицать отрицание какого-нибудь высказывания - то же, что утверждать это высказывание.
“ Неверно, что 2× 2¹ 4”

Законы идемпотентности. В алгебре логики нет показателей степеней и коэффициентов. Конъюнкция одинаковых “сомножителей” равносильна одному из них.

Законы коммутативности и ассоциативности. Конъюнкция и дизъюнкция аналогичны одноименным знакам умножения и сложения чисел.
В отличие от сложения и умножения чисел логическое сложение и умножение равноправны по отношению к дистрибутивности: не только конъюнкция дистрибутивна относительно дизъюнкции, но и дизъюнкция дистрибутивна относительно конъюнкции.

Смысл законов де Моргана (Август де Морган (1806-1871) - шотландский математик и логик) можно выразить в кратких словесных формулировках:
- отрицание логического произведения эквивалентно логической сумме отрицаний множителей.
- отрицание логической суммы эквивалентно логическому произведению отрицаний слагаемых.

Доказать законы логики можно:
1) с помощью таблиц истинности;
2) с помощью равносильностей.
Докажем законы склеивания и поглощения с помощью равносильностей:
1) (C Ú U) Ù ( Ú U) º (C + U) × ( + U) º C × + U × + U × U + C × U ºU × + U + C × U º U × +U (1 + C) º U × + U º U ( + 1) º U (Закон склеивания)

2) C Ù (C Ú U) º C × C +C × U º C +C × U º C (1 + U) º C (Закон поглощения)

Задание. Доказать законы логики с помощью таблиц истинности.

Тождественные преобразования

Упрощение формул.

Пример 1. Упростить формулу (АÚВ)· (АÚС)
Решение.
а) Раскроем скобки (A Ú B) · (A ÚC) º A · A Ú A · C Ú B · A Ú B · C
б) По закону равносильности A · A º A , следовательно,
A · A Ú A · C ÚB · A Ú B · C º A ÚA · C Ú B · A Ú B · C
в) В высказываниях А и А· C вынесем за скобки А и используя свойство АÚ1º 1, получим АÚА· СÚ B · A Ú B · C º A ·(1 ÚС) Ú B · A Ú B · Сº A ÚB · A Ú B· С
г) Аналогично пункту в) вынесем за скобки высказывание А.
AÚB · A Ú B · Сº A (1ÚB)ÚB · Сº A Ú B · С
Таким образом, мы доказали закон дистрибутивности.

2. Преобразования “поглощение” и “склеивание”

Пример 2. Упростить выражение АÚ A · B

Решение. A ÚA · B º A (1 Ú B) º A - поглощение

Пример 3. Упростить выражение A · B Ú A · - знаки логического сложения;
- знаки логического умножения.
А будут использованы:
- знаки отрицания и логического умножения;
- знаки отрицания и логического сложения.

Пример 5. Преобразовать формулу так, чтобы в ней не использовались знаки логического сложения.
Решение. Воспользуемся законом двойного отрицания, а затем формулой де Моргана.

Пример 6. Преобразовать формулу так, чтобы в ней не использовались знаки логического умножения.
Решение. Используя формулы де Моргана и закон двойного отрицания получим:

Среди возможных значений истинности лингвистической переменной Истинность два значения привлекают особое внимание, а именно пустое множество и единичный интервал , которые соответствуют наименьшему и наибольшему элементам (по отношению включения) решетки нечетких подмножеств интервала . Важность именно этих значений истинности обусловлена тем, что их можно интерпретировать как значения истинности не определено и неизвестно соответственно. Для удобства будем обозначать эти значения истинности символами и , понимая при этом, что и определяются выражениями

Значения неизвестно и не определено , интерпретируемые как степени принадлежности, используются также в представлении нечетких множеств типа 1. В этом случае имеются три возможности выражения степени принадлежности точки в : 1) число из интервала ; 2) (не определено ); 3) (неизвестно ).

Рассмотрим простой пример. Пусть

Возьмем нечеткое подмножество множества вида

В этом случае степень принадлежности элемента множеству есть неизвестно , а степень принадлежности есть не определено . В более общем случае может быть

где имеется в виду, что степень принадлежности элемента множеству частично неизвестна, причем член интерпретируется следующим образом:

. (6.56)

Важно четко понимать разницу между и . Когда мы говорим, что степень принадлежности точки множеству есть , мы имеем в виду, что функция принадлежности не определена в точке . Предположим, например, что - множество действительных чисел, а - функция, определенная на множестве целых чисел, причем , если - четное, и , если - нечетное. Тогда степень принадлежности числа множеству есть , а не 0. С другой стороны, если бы была определена на множестве действительных чисел и тогда и только тогда, когда - четное число, то степень принадлежности числа множеству была бы равна 0.

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

, (6.57)

. (6.58)

Применяя принцип обобщения, как в (6.25), получим

, (6.59)

После упрощения (6.59) сводится к выражению

. (6.61)

Другими словами, значение истинности высказывания и , где , есть нечеткое подмножество интервала , степень принадлежности которому точки равна (функции принадлежности ) на интервале .

Рис. 6.4. Конъюнкция и дизъюнкция значений истинности высказывания со значением истинности неизвестно ().

Аналогично находим, что значение истинности высказывания или выражается в виде

. (6.62)

Следует отметить, что выражения (6.61) и (6.62) легко получить с помощью описанной выше графической процедуры (см. (6.38) и далее). Пример, иллюстрирующий это, показан на рис. 6.4.

Обращаясь к случаю , находим

(6.63)

и аналогично для .

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

или в более привычном виде

где означает истинный , а - ложный . Поскольку есть , мы можем отождествить значение истинности неизвестно со значением истинный или ложный , т. е.

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

Поскольку универсальное множество значений истинности состоит лишь из двух элементов, целесообразно построить таблицы истинности для операций , и в этой четырехзначной логике непосредственно, т. е. без использования общих формул (6.25), (6.29) и (6.31). Так, применяя принцип обобщения к операции , сразу получаем

откуда с необходимостью следует, что

На этом пути мы приходим к обычному определению связки ⟹ в двузначной логике в виде следующей таблицы истинности:

Как показывает рассмотренный выше пример, понятие значения истинности неизвестно в сочетании с принципом обобщения помогает уяснить некоторые из понятий и соотношений обычных двузначной и трехзначной логик. Эти логики, конечно, можно рассматривать как вырожденные случаи нечеткой логики, в которой значением истинности неизвестно является весь единичный интервал, а не множество 0 + 1.

Значение истинности

Эта статья или раздел - грубый перевод статьи на другом языке (см. Проверка переводов). Он мог быть сгенерирован программой-переводчиком или сделан человеком со слабыми познаниями в языке оригинала. ¬(Шаблон:Mvar∧Шаблон:Mvar) ⇔ ¬Шаблон:Mvar ∨ ¬Шаблон:Mvar ¬(Шаблон:Mvar∨Шаблон:Mvar) ⇔ ¬Шаблон:Mvar ∧ ¬Шаблон:Mvar Многозначная логика Многозначная логика (например, нечеткая логика позволяет более двух значений истинности, возможно, содержащих некоторые внутренние структуры. Алгебраическая семантика Не все логические системы истинно-ценностные в том смысле, что логические связки могут быть интерпретированы как истина функций. Например, в интуиционистской логике отсутствует полный набор значений истинности, потому что его семантика, определяется в терминах доказуемости условия, а не непосредственно в терминах обязательной верности формул. В других теориях Интуиционистской теории типов использует типы вместо значений истинности. Топос теории использует значения истинности в особом смысле: истина значения топос является глобальным элементом х подобъектом классификатором. Имея значения истинности в этом смысле не имеет ценностной логики истины. См. также Ссылки Wikimedia Foundation . 2010 . Смотреть что такое "Значение истинности" в других словарях: Содержание, обозначенное тем или иным языковым выражением словом, предложением, знаком и т.п. Вопрос о З. языковых выражений исследуется лингвистикой, семиотикой и логической семантикой. Различают предметное, смысловое и экспрессивное З. языковых … Философская энциклопедия Значение истинности (в логике), значение, которое принимает Высказывание (предложение, суждение), рассматриваемое по отношению к отображаемому в нём содержанию. В обычной (классической) логике используются два И. з. «истинно», «ложно»; в… … Большая советская энциклопедия Таблица истинности это таблица, описывающая логическую функцию. Под «логической функцией» в данном случае понимается функция, у которой значения переменных (параметров функции) и значение самой функции выражают логическую истинность.… … Википедия Таблица, с помощью которой устанавливается истинностное значение сложного высказывания при данных значениях входящих в него простых высказываний. В классической математической логике предполагается, что каждое простое (не содержащее логических… … Словарь терминов логики Денотат (от лат. denotatum обозначенное), термин лингвистики и экстенсиональной логики, обозначающий 1) экстенсионал, 2) десигнат, 3) референт и 4) семантическое ядро значения. Содержание 1 Денотат как экстенсионал 2 Денотат как десигнат … Википедия Одна из возможных характеристик высказывания с точки зрения соответствия его описываемому фрагменту действительности. Если допускается, что каждое высказывание является либо истинным, либо ложным (т. е. что онолибо соответствует действительности … Словарь терминов логики Совокупность логических систем, опирающихся на многозначности принцип. В классической двузначной логике выражения при интерпретации принимают только два значения «истинно» и «ложно», в М.л. рассматриваются и др. значения, напр. «неопределенно»,… … Философская энциклопедия - (от лат. factum сделанное, совершившееся) 1) синоним понятий «истина», «событие», «результат»; нечто реальное в противоположность вымышленному; конкретное, единичное в отличие от абстрактного и общего; 2) в философии науки особого рода п … Философская энциклопедия - (в л о г и к е) – истинность предложения (суждения, высказывания), обусловленная, в отличие от т.н. логич. истинности, содержанием этого предложения. Иначе говоря, предложение является фактически истинным, когда его истинность зависит от значений … Философская энциклопедия Стереометрическая семантика - трактовка логики как науки о получении истинных следствий из истинных посылок все более уступает место более широкой концепции,связанной либо с обобщением понятия следования, основанного на традиционной истинностной оценке и на практических… … Проективный философский словарь Книги Как искренне поверить в Бога, или Единственное, что имеет значение для развития веры , Враджев В.. Прежде чем сделать первые шаги в духовную жизнь, каждый человек всегда задается вопросом:`Существует ли Бог на самом деле?`И такому человеку, привыкшему воспринимать окружающий мир с помощью…

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

Логика высказываний отвлекается от содержательной нагрузки высказываний и изучает их истинностное значение, то есть является ли высказывание истинным или ложным.

Рисунок сверху - иллюстрация явления, известного как "Парадокс лжеца". При этом, на взгляд автора проекта, такие парадоксы возможны только в средах, несвободных от политических заморочек, где на ком-то могут априори поставить клеймо лжеца. В естественном многослойном мире на предмет "истины" или "лжи" оцениваются только отдельно взятые высказывания . И далее на этом уроке вам представится возможность самим оценить на этот предмет немало высказываний (а затем посмотреть правильные ответы). В том числе сложных высказываний, в которых более простые связаны между собой знаками логических операций. Но прежде рассмотрим сами эти операции над высказываниями.

Логика высказываний применяется в информатике и программировании в виде объявления логических переменных и присвоения им логических значений "ложь" или "истина", от которых зависит ход дальнейшего исполнения программы. В небольших программах, где задействована лишь одна логическая переменная, этой логической переменной часто даётся имя, например, "флаг" ("flag") и подразумевается, что "флаг поднят", когда значение этой переменной - "истина" и "флаг опущен", когда значение этой переменной - "ложь". В программах большого объёма, в которых несколько или даже очень много логических переменных, от профессионалов требуется придумывать имена логических переменных, имеющих форму высказываний и смысловую нагрузку, отличающую их от других логических переменных и понятных другим профессионалам, которые будут читать текст этой программы.

Так, может быть объявлена логическая переменная с именем "ПользовательЗарегистрирован" (или его англоязычный аналог), имеющая форму высказывания, которой может быть присвоено логическое значение "истина" при выполнении условий, что данные для регистрации отправлены пользователем и эти данные программой признаны годными. В дальнейших вычислениях значения переменных могут меняться в зависимости от того, какое логическое значение ("истина" или "ложь") имеет переменная "ПользовательЗарегистрирован". В других случах переменной, например, с именем "ДоДняХОсталосьБолееТрёхДней", может быть присвоено значение "Истина" до некоторого блока вычислений, а в ходе дальнейшего исполнения программы это значение может сохраняться или меняться на "ложь" и от значения этой переменной зависит ход дальнейшего исполнения программы.

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

Логические операции над высказываниями

Для математических высказываний всегда можно сделать выбор между двумя различными альтернативами "истина" и "ложь", а для высказываний, сделанных на "словесном" языке, понятия "истинности" и "ложности" несколько более расплывчаты. Однако, например, такие словесные формы, как "Иди домой" и "Идёт ли дождь?", не являются высказываниями. Поэтому понятно, что высказываниями являются такие словесные формы, в которых что-либо утверждается . Не являются высказываниями вопросительные или восклицательные предложения, обращения, а также пожелания или требования. Их невозможно оценить значениями "истина" и "ложь".

Высказывания же, напротив, можно рассмотривать как величину, которая может принимать два значения: "истина" и "ложь".

Например, даны суждения: "собака - животное", "Париж - столица Италии", "3

Первое из этих высказываний может быть оценено символом "истина", второе - "ложь", третье - "истина" и четвёртое - "ложь". Такая трактовка высказываний составляет предмет алгебры высказываний. Будем обозначать высказывания большими латинскими буквами A , B , ..., а их значения, то есть истину и ложь, соответственно И и Л . В обычной речи употребляются связи между высказываниями "и", "или" и другие.

Эти связи позволяют, соединяя между собой различные высказывания, образовывать новые высказывания - сложные высказывания . Например, связка "и". Пусть даны высказывания: "π больше 3" и высказывание "π меньше 4". Можно организовывать новое - сложное высказывание "π больше 3 и π меньше 4". Высказывание "если π иррационально, то π ² тоже иррационально" получается связыванием двух высказываний связкой "если - то". Наконец, мы можем получить из какого-либо высказывания новое - сложное высказывание - отрицая первоначальное высказывание.

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

Пусть даны два произвольных высказывания A и B .

1 . Первая логическая операция над этими высказываниями - конъюнкция - представляет собой образование нового высказывания, которое будем обозначать A ∧ B и которое истинно тогда и только тогда, когда A и B истинны. В обычной речи этой операции соответствует соединение высказываний связкой "и".

Таблица истинности для конъюнкции:

A	B	A ∧ B
И	И	И
И	Л	Л
Л	И	Л
Л	Л	Л

2 . Вторая логическая операция над высказываниями A и B - дизъюнкция, выражаемая в виде A ∨ B , определяется следующим образом: оно истинно тогда и только тогда, когда хотя бы одно из первоначальных высказываний истинно. В обычной речи эта операция соответствует соединению высказываний связкой "или". Однако здесь мы имеем не разделительное "или", которое понимается в смысле "либо-либо", когда A и B не могут быть оба истинны. В определении логики высказываний A ∨ B истинно и при истинности лишь одного из высказываний, и при истинности обоих высказываний A и B .

Таблица истинности для дизъюнкции:

A	B	A ∨ B
И	И	И
И	Л	И
Л	И	И
Л	Л	Л

3 . Третья логическая операция над высказываниями A и B , выражаемая в виде A → B ; полученное таким образом высказывание ложно тогда и только тогда, когда A истинно, а B ложно. A называется посылкой , B - следствием , а высказывание A → B - следованием , называемая также импликацией. В обычной речи эта операция соответствует связке "если - то": "если A , то B ". Но в определении логики высказываний это высказывание всегда истинно независимо от того, истинно или ложно высказывание B . Это обстоятельство можно кратко сформулировать так: "из ложного следует всё, что угодно". В свою очередь, если A истинно, а B ложно, то всё высказывание A → B ложно. Оно будет истинным тогда и только тогда, когда и A , и B истинны. Кратко это можно сформулировать так: "из истинного не может следовать ложное".

Таблица истинности для следования (импликации):

A	B	A → B
И	И	И
И	Л	Л
Л	И	И
Л	Л	И

4 . Четвёртая логическая операция над высказываниями, точнее над одним высказыванием, называется отрицанием высказывания A и обозначается ~ A (можно встретить также употребление не символа ~, а символа ¬, а также верхнего надчёркивания над A ). ~ A есть высказывание, которое ложно, когда A истинно, и истинно, когда A ложно.

Таблица истинности для отрицания:

A	~ A
Л	И
И	Л

5 . И, наконец, пятая логическая операция над высказываниями называется эквивалентностью и обозначается A ↔ B . Полученное таким образом высказывание A ↔ B есть высказывание истинное тогда и только тогда, когда A и B оба истинны или оба ложны.

Таблица истинности для эквивалентности:

A	B	A → B	B → A	A ↔ B
И	И	И	И	И
И	Л	Л	И	Л
Л	И	И	Л	Л
Л	Л	И	И	И

В большинстве языков программирования есть специальные символы для обозначения логических значений высказываний, записываются они почти во всех языках как true (истина) и false (ложь).

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

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

Связка	Обозначение	Название операции
не		отрицание
и		конъюнкция
или		дизъюнкция
если..., то...		импликация
тогда и только тогда		эквивалентность

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

Пример 1.

1) (2 = 2) И (7 = 7) ;

2) Не(15 ;

3) ("Сосна" = "Дуб") ИЛИ ("Вишня" = "Клён") ;

4) Не("Сосна" = "Дуб") ;

5) (Не(15 20) ;

6) ("Глаза даны, чтобы видеть") И ("Под третьим этажом находится второй этаж") ;

7) (6/2 = 3) ИЛИ (7*5 = 20) .

1) Значение высказывания в первых скобках равно "истина", значение выражения во вторых скобках - также истина. Оба высказывания соединены логической операцией "И" (смотрим правила для этой операции выше), поэтому логическое значение всего данного высказывания - "истина".

2) Значение высказывания в скобках - "ложь". Перед этим зтим высказыванием стоит логическая операция отрицания, поэтому логическое значение всего данного высказывания - "истина".

3) Значение высказывания в первых скобках - "ложь", значение высказывания во вторых скобках - также "ложь". Высказывания соединены логической операцией "ИЛИ" и ни одно из высказываний не имеет значения "истина". Поэтому логическое значение всего данного высказывания - "ложь".

4) Значение высказывания в скобках - "ложь". Перед этим высказыванием стоит логическая операция отрицания. Поэтому логическое значение всего данного высказывания - "истина".

5) В первых скобках отрицается высказывание во внутренних скобках. Это высказывание во внутренних скобках имеет значение "ложь", следовательно, его отрицание будет иметь логическое значение "истина". Высказывание во вторых скобках имеет значение "ложь". Два этих высказывания соединены логической операцией "И", то есть получается "истина И ложь". Следовательно, логическое значение всего данного высказывания - "ложь".

6) Значение высказывания в первых скобках - "истина", значение высказывания во вторых скобках - также "истина". Два этих высказывания соединены логической операцией "И", то есть получается "истина И истина". Следовательно, логическое значение всего данного высказывания - "истина".

7) Значение высказывания в первых скобках - "истина". Значение высказывания во вторых скобках - "ложь". Два этих высказывания соединены логической операцией "ИЛИ", то есть получается "истина ИЛИ ложь". Следовательно, логическое значение всего данного высказывания - "истина".

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

1) "Пользователь не зарегистрирован";

2) "Сегодня воскресенье и некоторые сотрудники находятся на работе";

3) "Пользователь зарегистрирован тогда и только тогда, когда отправленные пользователем данные признаны годными".

1) p - одиночное высказывание "Пользователь зарегистрирован", логическая операция: ;

2) p - одиночное высказывание "Сегодня воскресенье", q - "Некоторые сотрудники находятся на работе", логическая операция: ;

3) p - одиночное высказывание "Пользователь зарегистрирован", q - "Отправленные пользователем данные признаны годными", логическая операция: .

Решить примеры на логику высказываний самостоятельно, а затем посмотреть решения

Пример 3. Вычислите логические значения следующих высказываний:

1) ("В минуте 70 секунд") ИЛИ ("Работающие часы показывают время") ;

2) (28 > 7) И (300/5 = 60) ;

3) ("Телевизор - электрический прибор") И ("Стекло - дерево") ;

4) Не((300 > 100) ИЛИ ("Жажду можно утолить водой")) ;

5) (75 < 81) → (88 = 88) .

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

1) "Если часы неправильно показывают время, то можно невовремя прийти на занятия";

2) "В зеркале можно увидеть своё отражение и Париж - столица США";

Пример 5. Определите логическое значение выражения

(p → q ) ↔ (r → s ) ,

p = "278 > 5" ,

q = "Яблоко = Апельсин" ,

p = "0 = 9" ,

s = "Шапка покрывает голову" .

Формулы логики высказываний

Понятие логической формы сложного высказывания уточняется с помощью понятия формулы логики высказываний .

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

Для обозначения высказываний, как и упомянутом примере, будем продолжать использовать буквы

p , q , r , ..., p 1 , q 1 , r 1 , ...

Эти буквы будут играть роль переменных, принимающих в качестве значений истинностные значения "истина" и "ложь". Эти переменные называются также пропозициональными переменными. Мы будем далее называть их элементарными формулами или атомами .

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

~, ∧, ∨, →, ↔,

а также символы, обеспечивающие возможность однозначного прочтения формул - левая и правая скобки.

Понятие формулы логики высказываний определим следуюшим образом:

1) элементарные формулы (атомы) являются формулами логики высказываний;

2) если A и B - формулы логики высказываний, то ~A , (A ∧ B ) , (A ∨ B ) , (A → B ) , (A ↔ B ) тоже являются формулами логики высказываний;

3) только те выражения являются формулами логики высказываний, для которых это следует из 1) и 2).

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

Пример 6. Пусть p - одиночное высказывание (атом) "Все рациональные числа являются действительными", q - "Некоторые действительные числа - рациональные числа", r - "некоторые рациональные числа являются действительными". Переведите в форму словесных высказываний следующие формулы логики высказываний:

6) .

1) "нет действительных чисел, которые являются рациональными";

2) "если не все рациональные числа являются действительными, то нет рациональных чисел, являющихся действительными";

3) "если все рациональные числа являются действительными, то некоторые действительные числа - рациональные числа и некоторые рациональные числа являются действительными";

4) "все действительные числа - рациональные числа и некоторые действительные числа - рациональные числа и некоторые рациональные числа являются действительными числами";

5) "все рациональные числа являются действительными тогда и только тогда, когда не имеет место быть, что не все рациональные числа являются действительными";

6) "не имеет места быть, что не имеет место быть, что не все рациональные числа являются действительными и нет действительных чисел, которые являются рациональными или нет рациональных чисел, которые являются действительными".

Пример 7. Составьте таблицу истинности для формулы логики высказываний , которую в таблице можно обозначить f .

Решение. Составление таблицы истинности начинаем с записи значений ("истина" или "ложь") для одиночных высказываний (атомов) p , q и r . Все возможные значения записываются в восемь строк таблицы. Далее, определяя значения операции импликации, и продвигаясь вправо по таблице, помним, что значение равно "лжи" тогда, когда из "истины" следует "ложь".

p	q	r					f
И	И	И	И	И	И	И	И
И	И	Л	И	И	И	Л	И
И	Л	И	И	Л	Л	Л	Л
И	Л	Л	И	Л	Л	И	И
Л	И	И	Л	И	Л	И	И
Л	И	Л	Л	И	Л	И	Л
Л	Л	И	И	И	И	И	И
Л	Л	Л	И	И	И	Л	И

Заметим, что никакой атом не имеет вида ~A , (A ∧ B ) , (A ∨ B ) , (A → B ) , (A ↔ B ) . Такой вид имеют сложные формулы.

Число скобок в формулах логики высказываний можно уменьшить, если принять, что

1) в сложной формуле будем опускать внешнюю пару скобок;

2) упорядочим знаки логических операций "по старшинству":

↔, →, ∨, ∧, ~ .

В этом списке знак ↔ имеет самую большую область действия, а знак ~ - самую маленькую. Под областью действия знака операции понимаются те части формулы логики высказываний, к которым применяется (на которые действует) рассматриваемое вхождение этого знака. Таким образом, можно опускать во всякой формуле те пары скобок, которые можно восстановить, учитывая "порядок старшинства". А при восстановлении скобок сначала расставляются все скобки, относящиеся ко всем вхождениям знака ~ (при этом мы продвигаемся слева направо), затем ко всем вхождениям знака ∧ и так далее.

Пример 8. Восстановите скобки в формуле логики высказываний B ↔ ~ C ∨ D ∧ A .

Решение. Скобки восстанавливаются пошагово следующим образом:

B ↔ (~ C ) ∨ D ∧ A

B ↔ (~ C ) ∨ (D ∧ A )

B ↔ ((~ C ) ∨ (D ∧ A ))

(B ↔ ((~ C ) ∨ (D ∧ A )))

Не всякая формула логики высказываний может быть записана без скобок. Например, в формулах А → (B → C ) и ~ (A → B ) дальнейшее исключение скобок невозможно.

Тавтологии и противоречия

Логические тавтологии (или просто тавтологии) - это такие формулы логики высказываний, что если буквы произвольным образом заменить высказываниями (истинными или ложными), то в результате всегда получится истинное высказывание.

Так как истинность или ложность сложных высказываний зависит лишь от значений, а не от содержания высказываний, каждому из которых соответствует определённая буква, то проверку того, является ли данное высказывание тавтологией, можно подставить следующим способом. В исследуемом выражении на место букв подставляются значения 1 и 0 (соответственно "истина" и "ложь") всеми возможными способами и с использованием логических операций вычисляются логические значения выражений. Если все эти значения равны 1, то исследуемое выражение есть тавтология, а если хотя бы одна подстановка даёт 0, то это не тавтология.

Таким образом, формула логики высказываний, которая принимает значение "истина" при любом распределении значений входящих в эту формулу атомов, называется тождественно истинной формулой или тавтологией .

Противоположный смысл имеет логическое противоречие. Если все значения высказываний равны 0, то выражение есть логическое противоречие.

Таким образом, формула логики высказываний, которая принимает значение "ложь" при любом распределении значений входящих в эту формулу атомов, называется тождественно ложной формулой или противоречием .

Кроме тавтологий и логических противоречий существуют такие формулы логики высказываний, которые не являются ни тавтологиями, ни противоречиями.

Пример 9. Составьте таблицу истинности для формулы логики высказываний и определите, является ли она тавтологией, противоречием или ни тем, ни другим.

Решение. Составляем таблицу истинности:

И	И	И	И	И
И	Л	Л	Л	И
Л	И	Л	И	И
Л	Л	Л	Л	И

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

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

Высказыванием называют повествовательное предложение, которое имеет определенное значение истинности: истина или ложь. Истинному высказыванию ставится в соответствии 1, ложному – 0. Высказывания обозначаются буквами латинского алфавита.

Примеры простых высказываний:

1. А= «Число 100 больше числа 10»

2. В= «Сегодня я в школу не пойду»

Задания.

1) Объясните, почему следующие предложения не являются высказываниями:

1. Какого цвета этот дом?

2. Число Х не превосходит единицы.

4. Посмотрите в окно.

5. Пейте томатный сок!

6. Эта тема скучна.

7. Валерий Леонтьев – популярный певец.

2) Приведите примеры простых высказываний, определите их истинность или ложность.

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

1. А= «Число 100 больше 10, но меньше 1000»

2. В= «Если завтра будет дождь, то в поход мы не пойдем»

Какие простые высказывания входят в сложные А и В?

В образовании сложных высказываний используются слова: и, или, тогда и только тогда, когда (в том и только в том случае), если..., то..., нет. Их называют логическими связками или логическими операциями.

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

Логические операции

1) Инверсия (операция отрицания или логическое отрицание, НЕ). Обозначается ù, ` .

Если А - истинное высказывание, то `А – ложное высказывание, и наоборот .

_ А

2) Конъюнкция (логическое умножение, соответствует союзу И). Обозначается Ù, × , & , математическим знаком умножения или опуская его.

Например: С = «Солнце светит и нет дождя».

Обозначим А = «Солнце светит», В= «нет дождя».

Тогда высказывание С можно записать: А Ù В (или А&В, А×В, АВ).

Таблица истинности:

А	В	А&В (АВ)

3) Дизъюнкция (логическое сложение, ИЛИ), имеет два различных значения. Следует различать исключающее «или» и неисключающее «или».

В русском языке союз «или» используется в двояком смысле.

Например, в предложении «Обычно в 8 вечера я смотрю теле­визор или пью чай» союз «или» взят в неисключающем (объедини­тельном) смысле, так как вы можете только смотреть телевизор или только пить чай, но вы можете также пить чай и смотреть телевизор одновременно, потому что мама у вас нестрогая. Такая операция называетсянестрогой дизъюнкцией или просто дизъюнкцией. (Если бы мама была строгая, то она разрешила бы или только смотреть телевизор, или только пить чай, но не совмещать прием пищи с просмотром телепередач.)

В высказывании «Данный глагол I или II спряжения» союз «или» используется в исключающем (разделительном) смысле.Такаяоперация называетсястрогой дизъюнкцией.

Примеры строгих и нестрогих дизъюнкций:

а) Операция дизъюнкция (логическое сложение, нестрогая дизъюнкция), соответствует неисключающему ИЛИ, обозначается Ú , +.

Строгая дизъюнкция истинна только тогда, когда одно высказывание истинно, а другое ложно.

4) Импликация . Выражается словосочетанием «если … то». Импликация А ® В истинна всегда, за исключением случая, когда А истинно, а В ложно . Таблица истинности импликации имеет следующий вид:

А В А®В 1

(Из опыта : Операция импликации (логического следования) является наиболее сложной для учащихся, так как она самая «формально опреде­ленная» и не подкрепляется «здравым смыслом». В процессе ее изучения имеет смысл поговорить о формальном исполнителе и его отличии от неформального .)

Примеры импликаций:

1) Если клятва дана, то она должна выполняться.

2) Если число делится на 9, то оно делится на 3.

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

Приведем примеры суждений, которые не только правомерно рассматривать в логике, но и которые к тому же имеют значение «истина»;

1) Если коровы летают, то 2 + 2 = 5.

2) Если я - Наполеон, то у кошки четыре ноги.

Объяснить операцию импликацию можно, например, следующим образом.

Пусть даны высказывания:

А = На улице дождь. В = Асфальт мокрый .

А®В = «Если на улице дождь, то асфальт мокрый.»

Тогда, если идет дождь (А = 1) и асфальт мокрый (В = 1), то это правильно. Но если вам скажут, что на улице идет дождь (А = 1), а асфальт остается сухим (В = 0), то вы посчитаете это ложью. А вот когда дождя на улице нет (А = 0), то асфальт может быть и сухим, и мокрым (например, только что проехала поливальная машина).

5) Операция эквиваленция обозначается знаками «, =, Û. Сложное высказывание А«В
(А эквивалентно В) истинно тогда и только тогда, когда и А и В истинны, или когда и А и В – ложны.

Сводная таблица логических операций

(заполняется учащимися самостоятельно):

Ниже приведена таблица логических операций и их перевода на естественный язык.

Операция	Обозначение	Перевод на естественный язык
Инверсия (отрицание)	Ā, ùА, не А	не А; неверно, что А
Конъюнкция (логическое произведение)	АВ, АÙВ, А и В, А and В, А´В, А&В, А×В	и А, и В; как А, так и В; А вместе с В; А несмотря на В; А, в то время как В
Дизъюнкция простая (логическая сумма, не исключающее ИЛИ)	А+В, А Ú В, А или В, А or В	А или В
Дизъюнкция строгая (исключающее ИЛИ)	А"В, А Å В	или А или В либо А, либо В
Импликация	А®В, АÞВ	Если А, то В; В если А; В необходимо для А; А достаточно для В; А только тогда, когда В; В тогда, когда А; все А есть В
Эквиваленция	А«В, АÛВ	А равно В; А эквивалентно В; А необходимо и достаточно для В; А тогда и только тогда, когда В

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

Упражнения.

1. Даны два высказывания:

А={Число 5 - простое},

В={Число 4 - нечетное},

Очевидно, что А=1, В=0.

В чем заключаются высказывания:

а) Ā, б) `В, в) АВ, г) А+В д) А®В

Какие из высказываний а) – г) истинны? Составьте таблицы истинности.

2. Найдите значения выражений:

а) (1 + 1) Ú (1 + 0);

б) ((1 + 0) + 1) + 1;

в) (А + 1) + (В + 0);

г) (0 Ù 1) Ù 1;

д) 1 Ù (1 Ù 1) Ù 1;

е) ((1 Ú 0) Ù (1 Ù 1) Ù (0 Ú 1);

ж) ((1 Ù А) Ú (В Ù 0)) Ú 1;

з) ((1 Ù 1) Ú 0) Ù (0 Ú 1);

и) ((0 Ù 0) Ú 0) Ù (1 Ú 1);

к) ((0 × 1) + (1 + 1)) × 1.

3. Переведите на язык алгебры логики высказывания:

1) «Я поеду в Москву, и если встречу там друзей, то мы интересно проведем там время»

2) «Если я поеду в Москву и встречу там друзей, то мы интересно проведем там время»

3) «Неверно, что если дует ветер, то солнце светит только тогда, когда нет дождя».

4) «Если будет солнечная погода, то ребята пойдут в лес, а если будет пасмурно, то пойдут в кино»

5) «Неверно, что если погода пасмурная, то дождь тогда и только тогда, когда нет ветра».

6) «Если урок по информатике будет интересным, то ни Миша, ни Света, ни Вика не будут смотреть в окно»

Решение:

1) М × (В ® И); 2) (М × В) ® И; 3) В ® С ®`Д;

4) (С ® Л) × (`С ® К); 5) П ® (Д « `В); 6) И ® `М ×`С ×`В

1) «Вам никогда не удастся создать мудрецов, если будете убивать в детях шалунов» (Ж.Руссо).

2) «Чтение художественной литературы – неоценимый источник познания жизни и законов ее борьбы».

4) «Мудрость – это способность предвидеть отдаленные последствия совершаемых действий, готовность пожертвовать сиюминутной выгодой ради больших благ в будущем и умение управлять тем, что управляемо, не сокрушаясь из-за того, что неуправляемо» (Ракофф).

6) «Верность друга нужна и в счастье, в беде же она совершенно необходима».

4. Являются ли высказываниями русские народные пословицы и поговорки? Приведите примеры. (Из опыта : Объявляется конкурс «Знаешь ли ты пословицы, которые являются высказываниями». Победителей обычно несколько, поощряются оценками и поощрительными аплодисментами одноклассников )

Самостоятельная работа №1.

(примерные задания в приложении 1, некоторые решения и ответы в приложении 2)

1) Решить логическую задачу табличным способом;

2) Записать сложные высказывания на языке алгебры логики;

3) Найти значение выражения.

Таблицы истинности

Итак, сложное высказывание принимает значение 1 или 0 в зависимости от значений простых высказываний, входящих в него.

Таблицу, показывающую, какие значения принимает сложное высказывания при всех сочетаниях (наборах) значений входящих в него простых высказываний, называют таблицей истинности сложного высказывания.

В `В А`В А`В А`В ® А

Из полученной таблицы видно, что значения формулы А`В ® А совпадают со значениями формулы А. Такие формулы называются равносильными . Для обозначения равносильности используют обычно знак равенства.

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

2. Определить число строк в таблице m= 2 n .

3. Определить количество столбцов в таблице: число переменных плюс число операций.

4. Выписать наборы входных переменных с учетом того, что они представляют собой натуральный ряд n–разрядных двоичных чисел от 0 до 2 n -1.

5. Провести заполнение таблицы истинности по столбцам, выполняя логические операции в соответствии приоритета операций.

Пример. Построить таблицу истинности для формулы F=A ® B&C

0

Упражнения.

1. Проверьте равносильность следующих формул с помощью таблиц истинности:

1) А (А + В) = А

2) А + АВ = А

3) А ® В = Ā + В

4) А ® В = `А ®`В

5) `А +`В = А В

6) А + В = Ā ×`В

2. Определите значение формулы: F= ((С+В)®В) × (АВ) ®В.