1. Высказывания. Логические операции над высказываниями. Сложные высказывания. Таблицы истинности. Тождественно истинные и тождественно ложные высказывания.

Логическое высказывание — повествовательное предложение, которое формализует некоторое выражение мысли. Это утверждение, которому всегда можно поставить в соответствие одно из двух логических значений: ложь (0, ложно, false) или истина (1, истинно, true). Логическое высказывание принято обозначать заглавными латинскими буквами.

Высказывательной формой называется логическое высказывание, в котором один из объектов заменён переменной. При подстановке вместо переменной какого-либо значения высказывательная форма превращается в высказывание. Пример: A(x) = «В городе x идет дождь.» A — высказывательная форма, x — объект.

Высказывание обычно имеет только одно логическое значение. Так, например, «Париж — столица Франции» — высказывание, а «На улице идет дождь» — не высказывание. Аналогично, «5>3» — высказывание, а «2+3» — не высказывание.

Логические высказывания принято подразделять на два вида: элементарные логические высказывания и составные логические высказывания.

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

Логическая связка — это любая логическая операция над высказыванием. Например, употребляемые в обычной речи слова и словосочетания «не», «и», «или», «если… , то», «тогда и только тогда» являются логическими связками.

Элементарные логические высказывания — это высказывания не относящиеся к составным.

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

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

Отрицание логического высказывания — логическое высказывание, принимающее значение «истинно», если исходное высказывание ложно, и наоборот.

Конъюнкция двух логических высказываний — логическое высказывание, истинное только тогда, когда они одновременно истинны.

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

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

Равносильность (эквивалентность) двух логических высказываний — логическое высказывание, истинное только тогда, когда они одновременно истинны или ложны.

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

Формула является тождественно ложной, если она ложна при любых значениях входящих в неё переменных

Если две формулы А и В “одновременно”, то есть при одинаковых наборах значений входящих в них переменных, принимают одинаковые значения, то они называются равносильными.

Таблица истинности — это таблица, описывающая логическую функцию.

2. Формулы логики высказываний. Принцип индукции для них. Теорема об единственности прочтения.

Базовыми понятиями логики высказываний являются пропозициональная переменная — переменная, значением которой может быть логическое высказывание, — и (пропозициональная) формула, определяемаяиндуктивно следующим образом:

1. Если P — пропозициональная переменная, то P — формула.

2. Если A — формула, то — формула.

3. Если A и B — формулы, то , и — формулы.

4. Других соглашений нет.

Знаки и (отрицание, конъюнкция, дизъюнкция и импликация) называются пропозициональными связками. Подформулой называется часть формулы, сама являющаяся формулой. Собственной подформулой называется подформула, не совпадающая со всей формулой.

Лемма 1. Если и – формулы и – начало то

Теорема 1(о единственност прочтения(представления)). Всякая неатомарная формула единственным образом представима в одном из следующих видов: где и – формулы.

Доказательство. Существование такого представления следует из определения формулы. Надо лишь доказать единственность. Понятно, что если представима в виде то её нельзя представить в виде и надо лишь применить предположение индукции к формуле Пусть представима в виде неоднозначно. Тогда Одна из формул является началом другой. Значит, по лемме 1 Но тогда и Это доказывает единственность.

Следствие. Пусть – формула ИВ. Тогда с каждым вхождением символа или символа в эту формулу однозначно связывается вхождение в подформулы, начинающейся с этого символа. Доказательство. Действительно, если в есть символ то при построении формулы ранее была построена формула начинающаяся с этого символа, причём – тоже формула. Формула как раз и является подформулой, начинающейся с данного вхождения символа Единственность следует из леммы 1. Аналогично разбираются случаи вхождения в символа (.