Mat_Logika_Algebra_i_ischislenie_vyskazyvany
.pdf
101
ВАРИАНТ N 29.
1)Построить вывод для: ├ (A B) ((A (B C)) (A C))
2)Выводима ли из (A v A) формула (A v A) ?
3)Три члена жюри голосуют нажатием на кнопку. Построить простейшую цепь, минимизированную по числу контактов, через которую ток проходит при условии голосования «ЗА» не менее двух членов.
|
|
|
|
|
|
|
ВАРИАНТ N 30. |
|
|
|
|
|
|
|
|
|
|
|||||||
1) |
Построить вывод для: (X1 ¬ X2) => X3 ├ ¬ X3 => X2 |
|
|
|
|
|
||||||||||||||||||
2) |
Выводима ли: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
x |
|
|
|
|
y |
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
( |
A v |
|
) |
(A v |
|
) ? |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
A |
A |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
3) |
Составить функцию |
|
|
|
|
|
z |
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
¬y |
|
|
|
|
проводимости схемы и |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
x |
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
построить |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
минимизированную по |
|
|
¬z |
|
|
|
|
|
|
¬x |
|
|
|||||||||||
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
числу контактов схему
ВАРИАНТ N 31.
1)Построить вывод для: (X1 X2) => X3 ├ (X1 => X3) & (X2 => X3)
2)Выводима ли формула: A (A A) ?
3)Составить релейно-контактную схему, минимизированную по числу контактов, для формулы: (X Y ) ((Y Z )& (Z X ))
102
ВАРИАНТ N 32.
1)Построить вывод для: ├ ((X1 => X2) => X3 ) => (X2 => X3)
2)Выводима ли (A B) v(B A) ?
3)Составить релейно-контактную схему, минимизированную по числу контактов, для формулы: (X Y )& ((Y Z ) (Z X ))
ВАРИАНТ N 33.
1)Построить вывод для: ├ (((X1 => X2) => X3) => X1 ) => ( X3 => X1)
2)Выводима ли ((A B) A) (A (B &A)) ?
3)Составить релейно-контактную схему, минимизированную по числу контактов, для формулы: (X Y ) (X & (Y v Z ))
ВАРИАНТ N 34.
1) Построить вывод для: ¬ X1 => (X2 => X3), ¬ X1 => X2 ├ X1 X3
2) Выводима ли из A B формула B A ? |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
3) Составить функцию |
|
|
|
|
|
z |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
¬y |
|
|
|
|
||||||||||||||
проводимости схемы и |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
построить |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
¬z |
|
|
|
|
|
|
|
¬x |
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
минимизированную по |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
числу контактов схему |
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
z |
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
¬z |
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
¬y |
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
103
ВАРИАНТ N 35.*
1)Построить вывод для: (A B) ├ ((C A) (C B))
2)Выводима ли (((A B) B) A) ?
3)Составить релейно-контактную схему, минимизированную по числу контактов, для формулы: (X (Y Z)) (Y X )
ВАРИАНТ N 36.*
1)Построить вывод для: ├ A (B (A&B))
2)Выводима ли из A v B формула
A v( |
|
& B)? |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
y |
|
|
|
z |
|
|
|
|
|||||
A |
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
3) Составить функцию |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
¬y |
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
x |
|
|
|
|
|
|
z |
|
|
||
проводимости схемы и |
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
построить |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
¬x |
|
|
|
¬y |
|
|
|
|
|
|
||
минимизированную по числу |
|
|
|
|
|
|
|
z |
|
|
||||||||
|
|
|
|
|
|
|
|
|
||||||||||
контактов схему |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
104
Приложение 4. Пример решения вариантов контрольных заданий по аксиоматическим теориям и переключательным схемам
ВАРИАНТ N 35.
1)Построить вывод для: (A B) ├ ((C A) (C B))
2)Выводима ли (((A B) B) A) ?
3)Составить релейно-контактную схему, минимизированную по числу кон-
тактов, для формулы: (X (Y Z)) (Y X )
РЕШЕНИЕ:
1)
1.├( A B) (C ( A B)) (А1)
2.├(C ( A B)) ((C A) (C B)) (А2)
3.├( A B) ((C A) (C B)) (Сл.1 к 1, 2)
4.( A B)├((C A) (C B)) (MP к 3)
2)По Теореме о полноте: если A – тавтология, то она выводима. Значит, для доказательства выводимости формулы достаточно, чтобы она являлась тавтологией – тождественно истинной формулой (истинной на всех оценках списка переменных). В противном случае формула не выводима.
Проведем доказательство методом от противного.
Для этого предположим, что существует оценка списка переменных, на
которой принимает ложное значение. Это возможно
только в случае, если из истинности посылок следует ложное заключение (по определению импликации), т.е. должно быть А – Ложь (следует из крайней правой импликации), и одновременно ((A B) B) – Истина. (A B) – Ис-
тина при любом В. Пусть В – Истина. Тогда ((A B) B) – Истина, и фор-
мула не является тавтологией, так как на оценке <Л, И> принимает значение Ложь. Значит (((A B) B) A) – не выводима.
105
3)
Минимизируем предложенную функцию по количеству вхождений переменных:
10 |
Z)) |
6.2 |
(X&¬ (¬Y |
Z)) |
(X (Y Z)) (Y ¬X) =¬ (¬X (¬Y |
(¬Y ¬X) = |
(¬Y ¬X) 6.=2,8 (X&Y&¬ Z) (¬Y ¬X) 4=.2 ((¬Y Y)&(¬Y (X&¬ Z))) ¬X15=.2 ¬X ¬Y (X&¬ Z) 4=.2 ((X ¬X)&(¬ Z ¬X)) ¬Y15=.2 ¬X ¬Y ¬ Z
Составим упрощенную схему цепи, заменяя конъюнкцию(&) последователь-
ным соединением, а дизъюнкцию ( ) параллельным: ¬z
¬y
¬x
ВАРИАНТ N 36.
1)Построить вывод для: ├ A (B (A&B))
2)Выводима ли из A v B формула A v(A & B)?
3) Составить функцию |
|
|
|
|
y |
|
|
|
z |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|||||
проводимости схемы и |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
¬y |
|
|
|
|
|
|
|
|
|
|
x |
|
|
|
|
|
|
|
||||
построить |
|
|
|
|
|
|
|
|
z |
|
|
||||
|
|
|
|
|
|
|
|
|
|
||||||
минимизированную по |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
числу контактов схему |
|
|
|
|
|
|
|
|
|
|
|
||||
|
¬x |
|
|
|
¬y |
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
z |
|
|
||||||
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
РЕШЕНИЕ:
1)
1.A, B ├B ( A & B) (П3)
2.A├B ( A & B) (Т. о д. к 1)
106
3.├B B (Т5)
4.A├B ( A & B) (Сл.1 к 2,3)
5.├ A (B ( A & B)) (Т. о д. к 4)
2)По Теореме о полноте: если A – тавтология, то она выводима. Значит, для доказательства выводимости формулы достаточно, чтобы она являлась тавтологией – тождественно истинной формулой (истинной на всех оценках списка переменных). В противном случае формула не выводима.
A B ├A ( A & B) верно тогда и только тогда, когда верно
├ ( A B) ( A ( A & B)) (по Теореме о дедукции и MP)
Составим таблицу истинности для формулы ( A B) ( A ( A & B)) .
|
|
|
|
|
A ( |
|
& B) |
A B |
( A B) ( A ( |
|
& B)) |
|
|
|
|
& B |
A |
||||||
A |
B |
|
|
A |
|||||||
|
A |
||||||||||
|
|
|
|
|
|
|
|
|
|||
Л |
Л |
|
|
Л |
|
Л |
Л |
И |
|||
|
|
|
|
|
|
|
|
|
|||
Л |
И |
|
|
И |
|
И |
И |
И |
|||
|
|
|
|
|
|
|
|
|
|||
И |
Л |
|
|
Л |
|
И |
И |
И |
|||
|
|
|
|
|
|
|
|
|
|||
И |
И |
|
|
Л |
|
И |
И |
И |
|||
|
|
|
|
|
|
|
|
|
|
|
|
Из таблицы истинности видно, что формула является тавтологией, т.е. выводима.
Ответ: формула выводима.
3) Составим функцию проводимости предложенной схемы, заменяя последовательное соединение конъюнкцией (&), а параллельное - дизъюнкцией ( ):
107
(y&z) (x&¬y&z) ( ¬x&¬y&z)
Минимизируем функцию по количеству вхождений переменных:
(y&z) (x&¬y&z) ( ¬x&¬y&z) 4=.1 (( ¬y&z)&(x ¬x)) (y&z)15.2=,14.1 ( ¬y&z)
(y&z) 4.1,15=.2,14.1 z
Составим упрощенную схему цепи:
z
108
Приложение 5. F1 к аксиоматическим теориям
A, A B ├─B |
MP − «modus ponens» |
|
|
Простейшие свойства |
|
|
|
Если Γ├─A и Γ Γ1, то Γ1 ├─A |
Св.1 |
Если Γ├─A, то Γ,B├─A |
Св.2 |
|
|
Γ,A├─A |
Св.3 |
|
|
Если Γ,B,C├─A, то Γ,C,B├─A |
Св.4 |
|
|
Если Γ├─A и Di Γ→ Γ1 ├─Di , то Γ1 ├─A |
Св.5 |
Если Γ,B├─A и Γ├─B, то Γ├─A |
Св.6 (удаление выво- |
|
димой гипотезы) |
Если Γ├─A, Γ├─B и A,B├─C, то Γ├─C |
Св.7 |
|
|
Если Γ├─A и Γ├─A B, то Γ├─B |
Св.8 (для АТ с MP) |
|
|
Аксиомы |
|
|
|
A (B A) |
A1 |
(A (B C)) ((A B) (A C)) |
A2 |
(¬A ¬B) (B A) |
A3 |
Теоремы |
|
|
|
├─ A A |
T1 |
|
|
Если ├─ A, то B → ├─ B A |
T2 |
|
|
├─ ¬A (A B) |
T3 |
|
|
├─ ¬¬A (¬¬A A) |
T4 |
|
|
├─ ¬¬A A |
T5 |
|
|
├─ A ¬¬A |
T6 |
|
|
Если Γ, A├─B, то Γ├─A B |
Т. о д. |
|
(теорема о дедукции) |
A B,B C ├─A C |
Сл.1 |
|
(правило силлогизма) |
├─ (A B) (¬B ¬A) |
Сл.2 |
|
|
Если Γ, A├─B, то Γ,¬B├─ ¬A |
Сл.3 (правило перевер- |
|
тывания) |
109 |
|
|
|
Производные правила вывода |
|
|
|
A & B├─ A |
П1 |
|
|
A & B├─ B |
П2 |
|
|
A,B├─ A & B |
П3 |
|
|
A├─ A B |
П4 |
|
|
B├─ A B |
П5 |
|
|
Если A├─ C и B├─ C, то A B├─ C |
П6 |
|
|
Если A├─ B и A├─ ¬B, то ├─ ¬A |
П7 |
|
|
110
|
СОДЕРЖАНИЕ |
|
ВВЕДЕНИЕ |
3 |
|
1. |
АЛГЕБРА ВЫСКАЗЫВАНИЙ |
4 |
1.1. Пропозициональные связки и таблицы истинности |
4 |
|
|
Таблицы истинности |
5 |
|
Логические формулы |
5 |
|
Основные равносильности |
7 |
1.2. |
Тавтологии |
8 |
|
Основные тавтологии |
8 |
|
Правильные рассуждения |
8 |
|
Схемы правильных рассуждений. |
9 |
1.3. Полнота в логике высказываний |
12 |
|
1.4. |
Совершенные формы |
13 |
|
Двойственные формулы |
16 |
|
Алгоритм построения СДНФ по таблице истинности |
16 |
|
Алгоритм построения СКНФ по таблице истинности |
17 |
|
Алгоритм построения СДНФ и СКНФ с использованием |
|
|
равносильностей |
17 |
|
Двухместные булевы функции |
20 |
|
Свойства операций системы M6 |
21 |
|
Многочлены Жегалкина |
21 |
2. |
ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ |
24 |
2.1. |
Аксиоматические теории |
24 |
|
Простейшие свойства выводимых формул |
25 |
|
Аксиоматическая теория Чёрча |
26 |
2.2. Теоремы аксиоматической теории Чёрча |
28 |
|
|
Теорема о дедукции |
30 |
2.3. Производные правила вывода для новых связок |
33 |
|
2.4. |
Полнота и непротиворечивость аксиоматической теории Чёрча |
36 |