ЛР_5_Логика
.docЛабораторная работа 5. Логические основы ЭВМ
Теоретическое обоснование
Логическое высказывание – это любое утверждение, относительно которого можно сказать истинно оно или ложно, т.е. соответствует оно действительности или нет.
Логические переменные – переменные, которые принимают только два значения –"истина" или "ложь", обозначаемые, соответственно, "1" и "0".
В основе работы современных ЭВМ лежат три основные логические операции:
1) НЕ – отрицание, обозначается знаком ¬ или чертой над логической переменной.
2) ИЛИ – дизъюнкция или логическое сложение, обозначается знаком v или +.
3) И
– конъюнкция
или логическое
умножение, обозначается знаком &,
или
или *.
Используя операции НЕ и ИЛИ можно получить операцию ЕСЛИ-ТО, которая выражается связками "если ..., то", "из ... следует", "... влечет ...", называется импликацией и обозначается знаком →.
Используя операции НЕ, ИЛИ, И можно получить операцию РАВНОСИЛЬНО, которая выражается связками "тогда и только тогда", "необходимо и достаточно", "... равносильно ...", называется эквиваленцией или двойной импликацией и обозначается знаком ↔ или знаком ~.
Приоритет (порядок выполнения) логических операций по убыванию:
- операции в скобках,
- операция отрицания,
- операция конъюнкции,
- дизъюнкция,
- импликация
- и в последнюю очередь – эквивалентность.
Таблица истинности представляет собой таблицу, устанавливающую соответствие между всевозможными наборами значений переменных и значениями функций.
|
X |
Y |
X |
X & Y |
X V Y |
X Y |
X Y |
|
0 |
0 |
1 |
0 |
0 |
1 |
1 |
|
0 |
1 |
1 |
0 |
1 |
1 |
0 |
|
1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
1 |
1 |
0 |
1 |
1 |
1 |
1 |
Функция, которая принимает:
-
значение "истина" для всех наборов значений переменных, называется тождественно истинной функцией или тавтологией;
-
значение "ложь" для всех наборов значений переменных, называется тождественно ложной функцией или противоречием;
-
для некоторых наборов значений переменных значение "истина", а для других – значение "ложь", называется выполнимой логической функцией.
Если две функции А и В при одинаковых наборах значений входящих в них переменных, принимают одинаковые значения, то они называются равносильными.
Для составления таблицы истинности для логических выражений надо:
-
Определить количество строк в таблице: К=2n, где n – количество переменных.
-
Вычислить количество столбцов в таблице = количество переменных + количество логических операций.
-
Установить последовательность выполнения логических операций в соответствии с приоритетом.
-
Построить таблицу истинности и заполнить значениями.
Пример: Составить таблицу истинности для функции F= ¬x&y v ¬(x v y) v x. Функция F содержит две переменные x и y .
Количество строк в таблице: К=2n=4.
Количество столбцов в таблице=2+6=8.
Последовательность действий:
1) x v y
2) ¬x
3) ¬( x v y)
4) ¬x&y
5) ¬x&y v ¬(x v y)
6) ¬x&y v ¬(x v y)v x
Строим таблицу истинности и заполняем значениями:
|
Переменные |
Промежуточные логические функции |
Результат |
|||||
|
x |
y |
x v y |
¬x |
¬( x v y) |
¬x&y |
¬x&y v ¬(x v y) |
¬x&y v ¬(x v y)vx |
|
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
|
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
|
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
Из таблицы видно, что при всех наборах значений переменных x и y, функция F=¬x&y v ¬( x v y ) v x принимает значение 1, то есть функция F является тождественно истинной функцией или тавтологией.
Задания: 1)Построить таблицу истинности и определить вид для логических функций: f=AvB&Cv(¬AvC) и z= AvB&C&(Av¬B→C).
2) Построить таблицу истинности логической функции F=
|
№ |
Логическая функция |
|
1 |
( ( X & Y ) Y ) ( X V Y ) |
|
2 |
( X V Y ) ( X & Y ) |
|
3 |
( X & ( Y V X ) ) ( X & Y ) |
|
4 |
( ( X V Y ) X ) ( Y & X ) ) |
|
5 |
( X V ( X & Y ) ) ( X V Y ) |
|
6 |
( ( X Y ) & X ) ( X V Y ) |
|
7 |
( ( X V Y ) & ( X V Y ) ) X |
|
8 |
( X & Y ) V ( X ( Y & X ) ) |
|
9 |
X & ( ( Y & X ) ( X V Y ) ) |
|
10 |
( X & Y ) ( X V Y ) |
|
11 |
A V ( B & A ) ( A & B ) |
|
12 |
( A V B ) ( A & B ) |
|
13 |
( A & ( B V A ) ) ( A & B ) |
|
14 |
( ( A V B ) A ) ( B & A ) ) |
|
15 |
( ( A V B ) & ( A V B ) ) A |
|
16 |
( A & B ) ( A V B ) |
|
17 |
( A & B ) V ( A ( B & A ) ) |
|
18 |
A & ( ( B & A ) ( A V B ) ) |
|
19 |
( A V ( A & B ) ) ( A V B ) |
|
20 |
( ( A B ) & A ) ( A V B ) |
|
21 |
( ( R V S ) & ( R V S ) ) R |
|
22 |
( R V ( R & S ) ) ( R V S ) |
|
23 |
R & ( ( S & R ) (R V S ) ) |
|
24 |
( ( R & S ) S ) ( R V S ) |
|
25 |
( R V S ) ( R & S ) |
|
26 |
( R & S ) V ( R ( S & R ) ) |
|
27 |
( ( R S ) & R ) ( R V S ) |
|
28 |
R V ( S & R ) ( R & S ) |
|
29 |
( R & ( S V R ) ) ( R & S ) |
|
30 |
( ( R V S ) R ) ( S & R ) ) |
|
31 |
( ( A & B ) B ) ( A V B ) |
Список рекомендуемой литературы
Андреева Е.В., Босова Л.Л., Филина И.Н. Математические основы информатики. Учебное пособие – М.: БИНОМ. Лаборатория знаний, 2005 -328 с.