Синтаксис логики высказываний

Синтаксис логики высказываний прост и имеет прямые синтаксические и семантические аналоги в естественных языках, что чрезвычайно облегчает нам понимание логики высказываний. Символами языка логики высказываний, составляющими ее алфавит, являются логические константы ИСТИНА и ЛОЖЬ, сокращенно обозначаемые буквами И и Л, логические переменные х, у, z, обозначаемые строчными буквами латинского алфавита, логические связки (И), (ИЛИ), (НЕ), ЭКВИВАЛЕНТНО, => (ВЛЕЧЕТ) и круглые скобки. Значениями логических переменных являются логические константы. Предложения языка логики высказываний, называемые также формулами или высказываниями, составляют в соответствии со следующими правилами:

Логические константы являются простыми предложениями;

Логические переменные также простые предложения;

Сложные предложения формируются из простых с помощью связок (И), (ИЛИ), (НЕ), (ЭКВИВАЛЕНТНО), => (ВЛЕЧЕТ);

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

Из предложений с помощью связок и скобок можно образовать новые предложения языка логики высказываний;

Связки имеют следующий порядок старшинства Ø,Ù,Ú,É,º т.е. связка Ø самая старшая, а связка º самая младшая.

Формулы логики высказываний, составленные по этим правилам, называют правильно построенными формулами или сокращенно формулами.

2.1.2. Семантика логики высказываний.

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

Пример 1. Студент, который не ходит на занятия и не занимается дома, не сдаст экзамен. Обозначим через x₁ событие: ходить на занятия; через x₂ событие – заниматься дома и через y – сдать экзамен. Тогда формальная запись на языке алгебры логике будет иметь вид:

`y=`x1 Ù`x2

Пример 2. Если истинно утверждение, что Иван и Мария являются родителями и Юры и Анны, то Юра и Анна являются братом и сестрой. Обозначим: x₁ – Иван, x₂ – Мария, x₃ – Юра, x₄ – Анна, y₁ – родители Юры, y₂ – родители Анны, y – Юра и Анна – брат и сестра.

y1=x1Ùx2, y2=x1Ùx2, y=y1Ùy2.

То же самое можно описать словами:

“Родители_Юры”=”Иван”Ù”Мария”

“Родители_Анны”=”Иван”Ù”Мария”

“Юра_и_Мария – брат_и_сестра”=”Родители_Юры”Ù”Родители_Анны”

Иначе говоря, интерпретация определяет семантику формул (предложений, высказываний) путем сопоставления переменных в формулах со свойствами объектов среды, а отношений между этими свойствами — с формулами. Это позволяет по значению формул после подстановки вместо переменных конкретных значений свойств судить о наличии или отсутствии у среды тех или иных совокупных свойств или отношений. Если дана какая-либо формула, то подстановка в формулу констант вместо ее переменных называется конкретизацией. Таким образом конкретизация является результатом интерпретации.

Будем полагать, что, употребляя формулу xÉy, мы вкладываем в нее смысл, вытекающий из следующего предложения: «Мы заявляем, что истинность высказывания «х влечет у» означает, что истинность х влечет истинность у, а больше мы ничего не заявляем».

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

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

С помощью алгебры логики можно записывать любое правило и предложение для СИИ.

2.1.3. Общезначимые формулы и их роль.

Формулы, истинные на всех наборах значений своих аргументов, называют общезначимыми формулами. Если какая-либо формула a является общезначимой, то этот факт обычно записывается с использованием знака общезначимости ½= который ставится перед формулой: |=a. Проверку формулы на общезначимость можно осуществить с помощью таблицы истинности: если формула истинна во всех строках таблицы истинности, то эта формула общезначима. Рассмотрим, например, формулу ØxÙ(ØyÚy)ÉxØx. Из таблицы ясно, что формула является общезначимой, т.к. значения переменных в последнем столбце всегда истинно.

x	y	Øx	Øy	ØxÚy	ØxÙ(ØyÚy)	ØxÙ(ØyÚy)ÉxØx

Ранее было заявлено, что истинность высказывания a₁Éa₂ всегда означает, что истинность a₁ влечет истинность a₂ (здесь a₁ и a₂ являются формулами логики высказываний). Потому, установив факт общезначимости формулы a₁Éa₂ и истинности a₁, всегда можно сделать заключение об истинности a₂. Таким образом, общезначимость формул вида a₁Éa₂, называемых импликативными формулами, является важным свойством для получения заключения об истинности a₂, называемого заключением, при истинности a₁, называемого посылкой. Для простоты импликативные формулы a₁Éa₂ будем называть так же, как и связку É, импликацией. В логике высказываний известно много общезначимых формул, называемых обычно законами логики высказываний. Наиболее известными являются следующие законы.

Коммутативные: x₁Ùx₂=x₂Ùx₁, x₁Úx₂=x₂Úx₁;

Дистрибутивные: x₁Ù (x₂ x₃)=(x₁Ùx₂)Ú(x₁Ùx₃), x₁Ú(x₂Ùx₃)=(x₁Úx₂)Ù(x₁Úx₃);

Ассоциативные: x₁Ù(x₂ Ùx₃)=(x₁Ùx₂)Ùx₃, и x₁Ú(x₂Úx₃)=(x₁Úx₂)Úx₃;

законы Де Моргана:

= , = ,

закон двойного отрицания: .

Кроме того, справедливы следующие соотношения:

, . , ,

Сложные формулы, как правило, можно упростить. Для этого можно использовать следующие эквивалентности:

– правила поглощения,

– правило склеивания,

– правило вычеркивания.

Их доказательства осуществляются путем построения соответствующих таблиц истинности.

Рассмотрим пример упрощения логической функции. Пусть

Последовательное применение приведенных выше правил дает:

= =

=( ) =() =1.

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

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

Установление истинности следствия по общезначимой импликативной формуле достаточно универсальный способ для вывода заключений, но требует проверки общезначимости последней. Если формула a₁ É a₂ не является общезначимой, то подобного заключения делать нельзя.

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

Дата добавления: 2014-12-27