Название работы	Кол-во страниц	Размер
Вопросы по курсу: Математическая логика и теория алгоритмов (2 курс)	1	30.21kb.
Основы алгебры логики основные понятия алгебры логики	2	397.25kb.
Алгебра логики. Решение задач с элементами алгебры логики	1	112.27kb.
Алгебра логики и логические основы компьютера Алгебра логики	1	39.45kb.
2. элементы логики предикатов формулы логики предикатов и их преобразование	4	501.01kb.
Законы алгебры логики Название закона Математическое выражение Коммутативность	1	54.61kb.
Алгебраические системы Операции и алгебры. N	1	194.95kb.
Отчет зав кафедрой алгебры и математической логики	1	169.44kb.
Рабочая учебная программа по дисциплине	3	651.69kb.
Курс лекций Красноярск, 2007 Сенашов, В. И	3	992.09kb.
"Основы логики, таблицы истинности"	1	40.83kb.
Логические операции	1	168.13kb.
Викторина для любознательных: «Занимательная биология»	1	9.92kb.

Билет №3

Формулы алгебры логики

С помощью логических операций над высказываниями из заданной совокупности высказываний можно построить различные сложные высказывания. При этом порядок выполнения операций определяется круглыми скобками: например (x&y) -> ¬z; x-> ¬(y v (x&z))

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

Принят ряд соглашений для упрощения записи - скобки можно опускать, придерживаясь следующего порядка действий: раньше всех конъюнкция, затем дизъюнкция, импликация и эквивалентность. Если над формулой стоит знак отрицания (¬), то скобки также можно опустить.

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

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

Можно заметить, что если формула содержит n простых высказываний, то она принимает 2ⁿ в значении или, то же самое что таблица истинности будет иметь 2ⁿ строк.

Равносильные формулы алгебры логики

Две формулы алгебры логики называются равносильными, если они принимают одинаковые логические значения при любом наборе значений входящих в формулу простых высказываний. АΞВ – равносильность.

Формула А называется тождественно истинной (тафталогией), если она принимает единицу в значении при всех наборах значений, входящих в нее переменных. Формула А называется тождественно ложной (противоречием), если она принимает значение ноль при всех входящих в нее переменных. Во многих случаях тождественную истинность/ложность можно определить простейшим ее анализом.

Равносильность обладает тремя свойствами:

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

X Y X|Y X ¬X X|X

0 0 1 1 0 0

0 1 1 0 1 1

1 0 1

1 1 0

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