15 Логика высказываний.

Высказывание — это некоторое утверждение в виде повествовательного предложения, по содержанию которого можно сказать, истинно оно или ложно. Примеры истинных высказываний: «Река Волга впадает в Каспийское море»; «Существуют чётные числа, делящиеся на 3»; «Луна — спутник Земли». Примеры ложных высказываний: «В Томске водятся кентавры»; «Варшава — столица

Японии»; «Всемирно известную сказку «Конёк-горбунок» написал один из десятиклассников 30-й школы г. Томска».

Существуют утверждения, которые меняли свою истинность по мере развития науки. Например: «Солнце вращается вокруг Земли». Это высказывание длительное время считалось истинным. Теперь же оно ложно.

Встречаются утверждения, относительно  истинности которых невозможно сказать что-либо определённое ввиду отсутствия способов их доказательства или опровержения. Например: «Между людьми существует телепатическая связь». По мере развития науки это утверждение может стать либо истинным, либо ложным.

В некоторых случаях утверждения объявляются истинными без каких-либо объяснений и доказательств. Например: «На плоскости через точку, лежащую вне прямой, можно провести только одну прямую, не пересекающую данной». Это утверждение Евклида. А Н.И. Лобачевский [28, c. 43; 49, c. 9—10] о том же утверждает совсем другое: «На плоскости через точку, лежащую вне прямой, можно провести сколько угодно прямых, не пересекающих данной». Во втором высказывании утверждается нечто, противоположное первому. Однако оба высказывания истинны! Возможно ли это? Да. Оба высказывания являются аксиомами, которые, как известно, принимаются истинными без доказательств.

Таким образом, утверждения могут быть истинными, ложными и не истинными и не ложными одновременно. Мы в дальнейшем будем рассматривать только такие утверждения, которые являются либо истинными, либо ложными. Для удобства высказывания условимся обозначать латинскими буквами. Например, можно считать, что A — это высказывание «Идёт дождь». Если оно является истинным, то пишут А = 1. Соответственно запись A = 0 обозначает: высказывание «Идёт дождь» ложно.

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

Определение булевой функции

Определение Булевой функцией f(x1, x2, ... , xn) называется произвольная функция n переменных, аргументы которой x1, x2, ... , xn и сама функция f принимают значения 0 или 1, т. е. xi  {0, 1}, i = 1, 2, ... , n; f(x1, x2, ... , xn) {0, 1}.

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

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

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

 

Таблица 2.1 – Представление булевой функции

x1       x2      x3	f(x1, x2, x3)
0      0      0 0      0      1 0      1      0 0      1      1 1      0      0 1      0      1 1      1      0 1      1      1	1 0 0 1 0 1 0 1

 

 

 

 

 

 

 

 

 

 

Для формирования столбца значений переменных удобен лексико-графический порядок, в соответствии с которым каждый последующий набор значений получается из предыдущего прибавлением 1 в двоичной системе счисления, например, 100 = 011+ 1.

Булева функция n переменных может иметь 2ⁿ наборов. Поскольку функция принимает только два значения, общее число булевых функций n переменных равно 2²ⁿ . Таким образом, функция одной переменой может иметь четыре значения:y = x; y = Øx (отрицание х); y = 0 (константа 0); y = 1 (константа 1).

Из них выделим функцию “отрицание x”(обозначается Øx). Эта функция представлена в таблице 2. 2.

 

Таблица 2.2 – Функция отрицание

х	Øx
0 1	1 0

 

Булевых функций двух переменных – 16. Те из них, которые имеют специальные названия, представлены в таблице 2.3

 

Таблица 2.3 – Булевы функции двух переменных

x1       x2	x1Vx2	x1& x2	x1x2	x1x2	x1 Å x2	x1 x2	x1 x2
0      0 0      1 1      0 1      1	0 1 1 1	0 0 0 1	1 1 0 1	1 0 0 1	0 1 1 0	1 0 0 0	1 1 1 0

 

В таблице 2.3 представлены следующие функции двух переменных:-

x₁Vx₂  – дизъюнкция;

x₁& x₂  – конъюнкция;

x₁Éx₂ – импликация;

x₁x₂  – эквивалентность;

x_1Å x₂ – сложение по модулю 2;

x₁x₂ – стрелка Пирса;

x₁ x₂ – штрих Шеффера.

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