Элементарные высказывания

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

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

Снег белый.

Париж - столица Италии.

Все люди смертны.

Сократ - человек.

Если снег горит, то остается зола.

Если на улице идет дождь, то влажность выше, чем при солнечной сухой погоде.

Не всякое предложение является высказыванием. Так, к высказываниям не относятся вопросительные и восклицательные предложения, поскольку говорить об их истинности или ложности нет смысла. Предложения “Шел снег”, “Площадь комнаты равна 20 м²”, “а² = 4” не являются высказываниями; для того, чтобы имело смысл говорить об их истинности или ложности, нужны дополнительные сведения: когда и где шел снег, о какой конкретной комнате идет речь, какое число обозначено буквой а. В последнем примере а может не обозначать конкретного числа, а быть переменной, вместо которой можно подставлять элементы некоторого множества, называемые значениями переменной.

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

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

Для обозначения лжи мы будем использовать символ 0, а для обозначения истины- символ 1.

Элементарные высказывания, таким образом, мы будем обозначать символами переменных, принимающих значения 0 или 1. Такие переменные будем называть логическими или булевыми переменными.

Пусть U={u₁, u₂, ..., u_n, ...} - исходный алфавит переменных. Чтобы избежать сложных обозначений для индексов переменных, мы будем употреблять в качестве метаобозначений (обозначений для произвольных символов алфавита U) символы x, y, z, ..., а также эти и другие символы с индексами.

Итак, логические переменные (элементарные высказывания) имеют вид:

x,y,z,..;

x₁ ,x₂,x₃,...;

Элементарные логические операции (функции)

Функция , определенная на множестве

и принимающая значения из множества {0, 1}, называется функцией алгебры логики или булевой функцией.

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

Таблица 2.A.

Легко видеть, что n переменных в совокупности принимают 2ⁿразличных значений. Для удобства мы употребляем стандартное расположение наборов значений переменных: если набор рассматривать как двоичную запись числа, то их расположение соответствует естественному расположению чисел 0, 1, ... , 2^n-1. Каждая функция f(x₁, x₂, ... , x_n) определяет отображение B²´B²´ ... ´B²®B². Поэтому естественно интерпретировать f как символ, обозначающий это отображение, а x₁, x₂, ... , x_nкак названия столбцов. В этом случае функции f(x₁, x₂, ... , x_n) и f(y₁, y₂, ... , y_n) будут задавать одно и то же отображение, а их таблицы будут отличаться только, быть может, названиями столбцов. Обозначим через P₂множество всех функций алгебры логики над алфавитом U, содержащее также и константы 0 и 1. Если зафиксировать n переменных x₁, x₂, ... , x_n, то различные таблицы будут отличаться лишь значениями в правом столбце. Поэтому справедливо следующее утверждение.

Теорема 2.1.Число p₂(n) всех функций из P₂, зависящих от переменных x₁, x₂, ... , x_n, равно .

Здесь следует обратить внимание на одно обстоятельство. Число функций алгебры логики, зависящих от заданных n аргументов, конечно. Поэтому, если нужно выяснить, обладают ли функции из этого конечного множества каким-либо свойством, достаточно осуществить перебор функций из данного множества. Однако числа p₂(n) с ростом n быстро растут:

p₂(1) = 4, p₂(2) = 16, p₂(3) = 256, p₂(4) = 65536, ... .

Таким образом, уже при сравнительно небольших значениях n (n ³ 6) перебор становится практически неосуществимым даже с использованием вычислительной техники. С ростом числа аргументов n таблица, задающая функцию, сильно усложняется. Так при n = 64 для заполнения такой таблицы со скоростью 10⁹ строк в секунду понадобится около 300 лет. Поэтому несмотря на простоту табличного задания функций алгебры логики, такой инструмент исследования функций крайне неэффективен, если не бесполезен, при больших значениях n. Необходимость разработки аналитического задания и методов исследования функций алгебры логики очевидна.

Переменная x_i(1£ i £ n) функции f(x₁, x₂, ... ,x_i-1, x_i, x_i+1, ... , x_n) из P₂называется существенной, если можно указать такие наборы

и

значений переменных, что . В противном случае переменную x_i называют несущественной или фиктивной переменной функции f(x₁, x₂, ... ,
x_i-1, x_i, x_i+1, ... , x_n).

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

Построение аналитической теории функций алгебры логики начнем с элементарных функций (операций).

Данные операции (функции) часто употребляются в математической логике и кибернетике и играют такую же роль, как, например, x + y в арифметике, x² в алгебре, sin(x) и e^x в анализе, поэтому их можно считать элементарными функциями.

Определим логические или булевские операции (функции) над элементарными высказываниями или логическими (булевскими) переменными.

1. Константы (нульместные операции):

0 - тождественный нуль (тождественная ложь),

1 - тождественная единица (тождественная истина).

2. Операции над одной переменной (одноместные, унарные операции):

отрицание, обозначается как или ù x, читается “не x” или “отрицание x”. Эту операцию можно задать следующей таблицей, в которой указано, какое значение функции (операции) соответствует каждому из значений переменной x:

3. Операции над двумя переменными (двухместные, бинарные операции)

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

Функция x Ùyназывается конъюнкцией x и y, обозначается x Ùy , или x&y , или x×y , или xy , или min(x,y) и часто читается как “x и y”.

Функция x Ú yназывается дизъюнкцией x и y, обозначается x Ú y или
max (x,y) и часто читается как “x или y”.

Функцияx®yназывается импликацией x и y, обозначается x®y или
x É y, часто читается как “x имплицирует y” или “из x следует y”.

Функция xºyназывается эквивалентностью (или эквиваленцией) x и y, обозначается xºy, или x ~ y, или x«y и часто читается “x эквивалентно y”.

Функция x+yназывается суммой по модулю 2 (или булевой суммой) x и y, обозначается x+y, или xÅy и часто читается “x плюс y”.

Функция x|yназывается штрихом (Шеффера) x и y, обозначается x|y и часто читается “x штрих y”, “не x или не y”. В технической литературе функция x|yназывается обычно “не - и” или антиконъюнкцией, так как она равна отрицанию конъюнкции.

Функция x¯yназывается стрелкой (Пирса) x и y, обозначается x¯y и часто читается “x стрелка y”, “ни x, ни y” или “не x и не y”. В технической литературе функция x¯yназывается обычно “не - или” или антидизъюнкцией, так как она равна отрицанию дизъюнкции.

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

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

.

Очевидно, что не всякая последовательность символов переменных, знаков логических операций и скобок будет формулой алгебры логики. Так, например, последовательности ® Ú x+y, x½y º z не могут рассматриваться как правильные формулы алгебры логики. Дадим индуктивное определение формулы.

Пусть U - множество переменных. Тогда множество формул алгебры логики над U определяется следующим образом:

1. Всякая переменная - формула.

2. Константы 0 и 1 - формулы.

3. Если А - формула, то ù А (или в другой записи ) - формула.

4. Если А и В - формулы, то (АÙВ), (АÚВ), (А®В), (А+В), (АºВ), (АïВ), (А¯В) - формулы.

5. Формулами являются те и только те выражения, которые могут быть получены из констант, переменных и логических связок за конечное число шагов 1- 4.

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

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

Две формулы А и В (или f₁ и f₂) будем называть равносильными (равными) и писать А=В (или f₁ = f₂), если они реализуют одну и туже фукнцию алгебры логики.

Очевидно, что если А¢ - подформула формулы А, то при замене любого ее вхождения на равную формулу В¢ формула А перейдет в формулу В, которая будет равна А.

Обычно принимаются следующие соглашения для сокращения записи формул:

* внешние скобки у формул опускаются;

* формула ù А записывается как ;

* считается, что операция отрицания старше любой другой операции, то есть если за связкой ù следует символ переменной (буква), то отрицание относится только к этой переменной, если же сразу после отрицания ù открывается скобка, то отрицание относится ко всему заключенному в скобки выражению;

* формула АÙВ записывается как А×В, или А&B, или АВ;

* связка Ù считается старше (сильнее) любой другой двухместной связки.

Эти соглашения позволяют, например, записать формулу

((((ùx)+y)Ùz)®((xÙ(ù y))Ú z))

в виде

.

Не нашли, что искали? Воспользуйтесь поиском по сайту: