close

Вход

Забыли?

вход по аккаунту

?

3-4

код для вставкиСкачать
матлогика
Билет №3
Формулы алгебры логики
С помощью логических операций над высказываниями из заданной совокупности высказываний можно построить различные сложные высказывания. При этом порядок выполнения операций определяется круглыми скобками: например (x&y) -> ¬z; x-> ¬(y v (x&z)) Всякое сложное высказывание, которое может быть получено из простых посредством применения операций отрицания, дизъюнкции, конъюнкции, импликации называется формулой алгебры логики.
Принят ряд соглашений для упрощения записи - скобки можно опускать, придерживаясь следующего порядка действий: раньше всех конъюнкция, затем дизъюнкция, импликация и эквивалентность. Если над формулой стоит знак отрицания (¬), то скобки также можно опустить.
Логическое значение формулы алгебры логики полностью определяется логическими значениями входящих в нее простых высказываний. Все возможные значения формулы в зависимости от значений входящих в нее простых высказываний можно получить с помощью таблицы истинности. Можно заметить, что если формула содержит n простых высказываний, то она принимает 2n в значении или, то же самое что таблица истинности будет иметь 2n строк.
Равносильные формулы алгебры логики
Две формулы алгебры логики называются равносильными, если они принимают одинаковые логические значения при любом наборе значений входящих в формулу простых высказываний. АΞВ - равносильность.
Формула А называется тождественно истинной (тафталогией), если она принимает единицу в значении при всех наборах значений, входящих в нее переменных. Формула А называется тождественно ложной (противоречием), если она принимает значение ноль при всех входящих в нее переменных. Во многих случаях тождественную истинность/ложность можно определить простейшим ее анализом.
Равносильность обладает тремя свойствами:
1) Свойство рефлексивности АΞА
2) Симметричность если АΞВ, то ВΞА
3) Транзитивность если АΞВ, и ВΞС, то АΞС
Между понятиями равносильности и эквивалентности существует следующая связь: если АΞВ, то А <-> В = 1 и наоборот.
Три группы равносильностей алгебры логики
1. Основные равносильности
1) x&x Ξx
2) x v xΞx, где 1) и 2) - законы идемпотентности
3) x&1Ξx
4) x v 1Ξ1
5) x&0Ξ0
6) x v 0Ξx
7) x&¬xΞ0 - закон противоречия
8) x v ¬xΞ1 - закон исключенного третьего
9) ¬(¬х) Ξх - закон снятия двойного отрицания
10) x&(y v x) Ξx 11) x v (y&x) Ξx, где 10) и 11) - законы поглощения
Докажем 1 закон поглощения LΞx&(y v x)
Пусть х=1, тогда y v x = y v 1 = 1 => x&(y v x)=1
Пусть х=0, тогда по определенной операции конъюнкции L=0, а раз так то во всех случаях LΞx
2. Равносильности, выражающие одни логические операции через другие
1) x <-> y Ξ (x -> y)&(y -> x)
2) x -> y Ξ ¬x v y
3) ¬(x & y) Ξ ¬x v ¬y
4) ¬(x v y) Ξ ¬x & ¬y
5) x & yΞ¬(¬x v ¬y)
6) x v yΞ¬(¬x & ¬y)
Равносильность 5 и 6 получаются из равносильностей 3 и 4.
Докажем 1 равносильность: Пусть х и у принимают одинаковые логические значения, тогда формулы x <-> y, x -> y, y -> x будут равны 1, тогда будет истиной и (x -> y)&(y -> x); при одинаковых значениях х и у левая и правая часть равны. Пусть х и у разные, тогда x <-> y =0, x -> y =0.
Из равносильностей второй группы следует, что любую формулу алгебры логики можно заменить на равносильную ей, но содержащую только две функции: & и ¬ или v и ¬. Применяя равносильность 5 мы можем & заменять на v и ¬ равносильность 6 - на & и ¬.
Штрих Шеффера. Существует операция, которая не входит в список тех пяти операций классической алгебры логики, которая позволяет выразить любую из них через себя.
x|y Ξ ¬(x&y)¬x Ξ x|x XYX|YX ¬X X|X
0011 0 0
0110 1 1
101
110
3. Равносильности, выражающие основные законы алгебры логики.
1) x&y Ξ y&x
2) x v y Ξ y v x
3) x&(y&z) Ξ (x&y)&z
4) x v (y v z) Ξ (x v y) v z
5) x&(y v z) Ξ (x&y) v (x&z)
6) x v (y&z) Ξ (x v y)&(x v z)
Справедливость первых четырех равносильностей следует непосредственно их операций конъюнкции и дизъюнкции. Рассмотрим 5 и 6 равносильности.
Во всех равносильностях заменим знак Ξ на =, знак v на +, знак & на * и получим известные законы алгебры чисел. В первых пяти случаях мы получим законы, которые выполняются в алгебре логики, а в шестом нет. Докажем шестую равносильность:
1) Пусть х=1, тогда будут истинны: x v (y&z) =1
x v y =1
x v z =1
2) х =0, тогда x v (y&z) = y&z
x v y = y
x v z = z
Автор
lovematanfo
Документ
Категория
Без категории
Просмотров
63
Размер файла
18 Кб
Теги
билет
1/--страниц
Пожаловаться на содержимое документа