Методические рекомендации (стр. 2 )

Свойства логических операций

1)  ХÚУ = УÚХ (переместительное свойство дизъюнкции);

2)  Х^У = У^Х (переместительное свойство конъюнкции);

3)  ХÚ (УÚ Z) = (Х Ú У) Ú Z – сочетательное свойство;

4)  Х ^ (Y ^ Z) = (X ^ Y) ^ Z - сочетательное свойство;

5)  Х ^ (Y Ú Z) = ( X ^ Y)Ú ( X ^ Z) – распределительное свойство;

6)  Х Ú (Y ^ Z) = ( X Ú Y) ^ ( X Ú Z) – распределительное свойство;

7)  ;

8)  ;

9)  ;

10);

11) X ^ (X Ú Z) = X,

X Ú (X ^ Y) = X – закон поглощения;

12) - закон противоречия;

13) X Ú - закон исключенного третьего;

X Ú X = X, X ^ X = X.

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

Пример: Доказать, что Х®У = .

Решение: .

Определение 5. Х~У есть высказывание, истинное тогда и только тогда, когда Х и У оба истинны или оба ложны. Это высказывание называется эквивалентностью (Х эквивалентно У).

Таблица истинности:

Х	У	Х~У
1	1	1
0	1	0
1	0	0
0	0	1

1)  Х~ У= (Х^Y) Ú ;

2)  Х~ У= (Х®У) ^ (У®Х).

Определение 6. Две формулы равносильны, если при любых значениях переменных, входящих в эти формулы, они принимают одинаковые значения.

Некоторые свойства равносильности:

равносильно Х;

Х ^ X равносильно X;

X Ú X равносильно X;

равносильно Y;

равносильно .

истинно, ложно.

Применение алгебры высказываний:

Пример (Логическая задача):

На вопрос, кто из трех студентов изучал логику, был получен правильный ответ: если изучал первый, то изучал и второй, но не верно, что если изучал третий, то изучал и второй. Кто из студентов изучал логику?

Решение: Обозначим через Х1, Х2, Х3 – высказывания, состоящие в том, что I, II, III студенты изучали логику. Из задачи следует истинность высказывания:

,

т. к. - ложно. Значит, - ложно.

Из истинности S вытекает истинность отсюда вытекает, что логику изучал третий студент, а первый и второй не изучали.

Алгебра высказываний применяется при анализе рэлейноламповых схем. Под переключательной схемой мы будем понимать схематическое изображения, какого либо устройства, содержащего только двухзначные переключатели, т. е. переключатели, которые могут находиться в двух состояниях: в замкнутом (ток проходит) и разомкнутом (ток не проходит). Связь между переключательными схемами и алгеброй высказываний устанавливается следующим образом. Каждому переключателю ставится в соответствии высказывания, истинное тогда, когда переключатель замкнут, и ложное, если переключатель разомкнут. На схемах переключатели будем обозначать теми же буквами, что и соответствующие им высказывания.

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

Пример 1:

( Х ^ У) Ú (Х ^ Z) = X ^ (Y Ú Z);

X ^ (YÚ Z).

Эти две схемы эквивалентны, но вторая схема содержит меньше переключателей, поэтому она предпочтительнее.

Пример 2: Упростить схему

( Х ^ Y) Ú ((X Ú Z) ^ ) = (X ^ Y) Ú (X ^ ) Ú (Z ^ ) =

= X ^ (Y Ú ) Ú (Z ^ ) = X Ú (Z ^ ).

Тогда схема имеет вид

Вторая схема оптимальна, т. к. меньше переключателей.

Предикаты

Наряду с высказываниями приходится иметь дело с различными утверждениями (предложениями, предикатами), зависящими от одной или нескольких переменных.

Например, Х+1>0 зависит от Х. При Х = 0 оно истинно, а при Х = -2 ложно.

Предложения (предикаты), зависящие от переменных, будем обозначать Х(n), У(х), Z(х, у) и т. д. Предложения Р(х), , не является высказыванием, если оно рассматривается на всем множестве U. Но если Р(х) рассматривать при некотором конкретном значении х = а, то утверждение Р(а) будет либо истинным, либо ложным, т. е. будет высказыванием. Множества U, на котором задано предложение Р(х), можно разбить на два множества. Одно подмножество содержит те элементы U, для которых Р(х) истинно. Оно называется множеством истинности предложения Р(х). Другое подмножество состоит из тех элементов U, для которых Р(х) ложно. Если первое из них обозначим через , то второе множество будет и тогда получим . Для предложений, зависящих от переменной, так же, как и для высказываний, можно ввести логические операции.

Например, Отрицанием предложения называется предложение, определенное на том же множестве U и обращающееся в истинное высказывание для тех и только тех значений Х, для которых Р(х) ложно, обозначаются . Аналогично определяются и другие логические операции.

Знаки общности и существования

С предложениями, зависящими от переменных, связаны два вида часто встречающихся утверждения:

1) Предложение Р(х), хÎU обращается в истинное высказывание хотя бы для одного элемента множества U. Тогда пишут кратко: (х) Р(х) – существует точное значение хÎU, что Р(х) истинно.

- знак существования (перевернутая буква английского слова Exists – существует)

2) Предложение Р(х), хÎU обращается в истинное для всех элементов множества U.

Тогда пишут кратно: (Р(х) истинно для всех хÎU).

- знак общности (перевернутая первая буква английского слова All – все).

Примеры:

1) Даны два высказывания:

Х: «Петров учится в торговом институте»,

Y: 7 ≤ 5.

Определить, какие из следующих высказываний: а) , б) , в) → , г) → истинны, если известно, что – истинное высказывание.

Решение:

а) – истинно, т. к. - истинно;

б) – ложно, т. к. - ложно;

в) → – истинно, т. к. - ложно;

г) → – ложно, т. к - истинна, - ложно.

2) Истинно или ложно высказывание () ( ( )), если Y и Х – ложные, а Z – истинное высказывание.

Решение:

= – истинно, т. к. Х – ложно – истинно, т. к. – ложно.

Значит, ( ) – истинно, значит, () ( ( )) – истинна.

3) Какие из следующих высказываний равносильны

а) , б) , в) , г) , д) ?

Решение: = , = = .

Ответ: а) и б) равносильны;

4) Упростить схему:

 

Решение:

S = ()((()))) = () () () =

=()() = (()) = ()() = ().

 

5) Студентам объявили: «в понедельник буде одна пара бухучёт и одна математика, причём, если на первой паре математики не будет, то бухучёт будет на второй паре, если третья пара не математика, то четвёртая пара бухучёт, а если математика будет на первой паре, то бухучёт на пятой паре». Определить, на какой паре будет бухучёт и на какой математика?

Решение:

Пусть х1 – математика будет на I паре;

х3 – математика будет на III паре;

y2 – бухучёт будет на II паре;

y4 – бухучёт будет на IV паре;

y5 – бухучёт будет на V паре.

S = () () () = (() ()) () = (() () ()()) () = (() ()) () = () () () () =

Ответ: бухучёт на II паре, математика на III паре.

6) На множестве всех действительных чисел даны два предложения (предиката):

У(х): «уравнение (относительно t) »,

Z(х): = .

Найти множество истинности для предложений:

а) У(х), б) Z(x), в) У(х) Z(x), г) У(х) Z(x).

Решение:

а) Уравнение равносильно уравнению . При уравнение имеет решение. Значит, множеством истинности У(х) является множество У = (-∞; -2] [2; +∞).

б) =

|| ‌‌‌‌‌‌=

. . z = (-∞; 3].

в) У(х) Z(х):

У(х) Z(х) = R

г) У(х) Z(x) = (-∞; -2] [2; 3).

7) Дана система уравнений:

Определить, при каких значениях истинно каждое из следующих утверждений:

1)  при любом система имеет хотя бы одно решение,

2)  существует , при котором система имеет хотя бы одно решение.

Решение:

Если , то система имеет решение при любом ;

Если , то , .

При система имеет вид

Не имеет решения при .

При не имеет решения, например, при .

Итак, если , , то система имеет решение при любом «с».

Если ,то система имеет решение при .

Если , то система имеет решение при .

Таким образом, при любом существует , при котором система имеет решение.

Ответ: 1) – любое число, кроме , ;

2) – любое число.

8) Упростить логическое выражение .

Решение:

.

9) Построить таблицу истинности: , .

10) Упростить, используя свойства: , , , .

11) Упростить: .

Решение:

.