Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

188 Рассмотрим , например , выражение N(x&y) . Легко видеть , что N(x&y)= 1 - min (x,y)= max( 1 -x, 1 -y)=(Nx) ∨ (Ny). Аналогичным образом можно получить , что N(x ∨ y)=(Nx)&(Ny). Следова - тельно , в этой логике выполняются законы де Моргана . Имеются и другие сходства с двузначной логикой , но есть и различия , например , не выполняется закон исключённого третьего , т . е . х ∨ (Nx) не всегда истинно ; есть и другие раз - личия . Трёхзначная логика Гейтинга . В двузначной логике являются тавто - логиями как x ⇒ ¬¬ x , так и ¬¬ x ⇒ x . Из предположения , что тавтологией мож - но считать только формулу x ⇒ ¬¬ x, Гейтинг разработал новую трёхзначную логику . Операции Гейтинга вводятся согласно следующей таблице . Из таблицы видно , что конъюнкция и дизъюнкция определены следую - щим образом : x & y=min(x, y), x ∨ y=max(x, y), а импликация по формуле : x ⇒ y= 1 , если x ≤ y, x ⇒ y=y , если x > y . В этой логике , как и в логике Лукасевича , если оставить только значения 0 и 1 ( исключить третье значение – значение ½), то получим обычную двузнач - ную логику . х у Nx x&y x ∨ y x ⇒ y х ≡ у 0 0 0 0 ½ 1 1 0 0 0 0 ½ 1 1 1 1 1 0 0 ½ ½ ½ 0 ½ 1 ½ 0 ½ ½ ½ ½ 1 0 1 1 0 1 ½ 1 1 1 0 ½ 1 0 0 ½ 1 1 1 1 0 ½ 1 0 ½ 1 Трёхзначные логики Рейхенбаха , Бочвара и Клини В настоящее время имеется много вариантов построения трёхзначных ло - гик . Наиболее известными являются пять трёхзначных логик . К ним относятся указанные логики Лукасевича и Гейтинга , а также трёхзначные логики Рейхен - баха , Бочвара и Клини . Для сравнения этих логик положим , что истина , неоп - ределённость и ложь обозначены через 1, ½ и 0 соответственно . Отметим , что их создатели обозначили указанные значения по разному . Также единым обра - зом обозначим операции : конъюнкцию – & , дизъюнкцию – ∨ , импликацию – ⇒ и эквивалентность – ≡ . В каждой из этих логик есть отрицание , такое , что х =1 - х ( выше в логиках Лукасевича и Гейтинга отрицания для x обозначались через