Формулы алгебры логики.

2.1 Формулы алгебры логики.С помощью логических операций над высказываниями из простейших высказываний можно строить высказывания более слож­ные. При этом порядок выполнения операций указывается скобками. Например, можно построить такое высказывание: «Если Омск находится на берегу Волги и кислород – газ, то 2+3=5». Построенное высказывание символичес­ки записывается так: (А /В)С. Это высказывание звучит странно, но нас интересует не содержание этого высказывания, а его логическое значение. Логическое значение составного высказывания может быть определено, исходя из логических значе­ний исходных высказываний А, В, С и схемы по которой из исходных высказываний построено сложное выска­зывание.

Такая схема построения со­ставного высказывания может быть применена к различ­ным конкретным высказываниям, а не только к высказы­ваниям А, В, С . Поэтому ее можно записать в виде (X/Y) Z, где X, Y, Z–некоторые пере­менные, вместо которых можно подставить любые элементарные высказывания. Перемен­ные, вместо которых можно подставлять любые элементарные высказывания, называют высказывательными или пропозициональными переменными. С помощью высказывательных переменных и символов логических операций любое сложное высказывание можно формализовать, то есть заменить формулой, выражающей его логическую структуру. Эта формула называется формулой алгебры логики.

Теперь сформулируем точное определение формулы ал­гебры высказываний.

Определение формулы алгебры высказываний.

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

2. Если и – формулы алгебры высказываний, то выражения , , , и также являются формулами алгебры высказываний.

3. Никаких других формул алгебры высказываний, кроме получающихся согласно пунктам 1 и 2, нет.

Для составления формулы сложного высказывания нужно:

1) выделить все элементарные высказывания и логические связки, образующие данное составное высказывание;

2) заменить их соответствующими символами;

3) расставить скобки в соответствии со смыслом данного высказывания.

Для упрощения записи формул принят ряд соглашений:

1) скобки можно опускать, если над формулой стоит знак отрицания;

2) можно не заключать в скобки формулы, не являющиеся частями других формул;

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

Пример.

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

А: «Две плоскости параллельны»;

В: «Две плоскости имеют общие точки»;

С: «Две плоскости совпадают».

Тогда данное высказывание в виде формулы записывается так: .

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

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

В результате получим таблицу:

 

 
 
 
 
 

 

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

Если формула содержит n элементарных высказываний, то таблица содержит строк.