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

Рассмотрим, например, выражение . Легко видеть, что N(x&y)= 1- min (х,у)= max(\-x,\-y)=(Nx)v(Ny). Аналогичным образом можно получить, что N(xvy)=(Nx)&(Ny). Следова­ тельно, в этой логике выполняются законы де Моргана. Имеются и другие сходства с двузначной логикой, но есть и различия, например, не выполняется закон исключённого третьего, т.е. xv(Nx) не всегда истинно; есть и другие раз­ личия. Трёхзначная логика Гейтинга. В двузначной логике являются тавто­ логиями как —1—х, так и х. Из предположения, что тавтологией мож­ но считать только формулу —i —ix, Гейтинг разработал новую трёхзначную логику. Операции Гейтинга вводятся согласно следующей таблице. Из таблицы видно, что конъюнкция и дизъюнкция определены следую­ щим образом: x&y=min(x, у), xvy=max(x, у), а импликация по формуле: х^у =1, если х<у, х^у=у, если х>у. В этой логике, как и в логике Лукасевича, если оставить только значения О и 1 (исключить третье значение - значение Уг), то получим обычную двузнач­ ную логику. X У Nx х&у хуу х^у х=у 0 0 1 0 0 1 1 0 У2 0 У2 1 0 0 1 0 1 1 0 0 У2 0 У2 0 0 У2 У2 У2 1 1 У2 1 У2 1 1 У2 1 0 0 0 1 0 0 1 У2 У2 1 У2 У2 1 1 1 1 1 1 Трёхзначные логики Рейхенбаха, Бочеара и Клини В настоящее время имеется много вариантов построения трёхзначных ло­ гик. Наиболее известными являются пять трёхзначных логик. К ним относятся указанные логики Лукасевича и Гейтинга, а также трёхзначные логики Рейхен­ баха, Бочвара и Клини. Для сравнения этих логик положим, что истина, неоп­ ределённость ж ложь обозначены через 1, Уг и О соответственно. Отметим, что их создатели обозначили указанные значения по разному. Также единым обра­ зом обозначим операции: конъюнкцию - &, дизъюнкцию - v, импликацию - ^ и эквивалентность - ^ В каждой из этих логик есть отрицание, такое, что х =1- X (выше в логиках Лукасевича и Гейтинга отрицания для х обозначались через 188