Тест «Виды ссылок. Логические функции» 9 класс
Тестовые задания на тему «Виды ссы лок. Логически е функции».
Инструкция
Выберите букву, со ответствующую ва рианту правильного ответа.
За каждый пр авильный ответ дается балл. Баллы, полученные Вами за
все выполненные з адания, суммируютс я. Постарайтесь выполнить как
можно больше заданий и набрать к ак можно больше б аллов.
1. Среди приве денных ответов от ыщите форму лу для электронной таблиц ы:
в) А1=А3В8+ 12
г) А1=А3*В8+1 2
2. Сколько су ществует видов ссыл ок в Excel ?
3. Выберите в ид ссылки, несу ществующей в таблич ном процессоре Exce l :
а) относительна я
б) обязательная
в) абсолютная
г) смешанная
4. Абсолютные ссылки при перемещен ии или копирова нии в электронной
а) не изменяются
б) преобразу ется вне зависимости от нового положен ия формулы
в) преобразу ются в зависимости от н ового п оложения форму лы
г) преобразу ются в зависимости от дли ны формулы
д) в одних слу чаях меняются, в дру гих нет
5. Относительные с сылки при перемещ ении или копировании в элект ронной
а) не изменяются
б) преобразу ется вне зависимости от нового положен ия формулы
в) преобразу ются в зависимости от н ового п оложения форму лы
г) в одних слу чаях меняются, в дру гих нет
6. При копир овании смешанной ссылк и C $3, вид:
а) не изменится целиком
б) не изменитс я номер строки
в) не изменится н омер столбца
7. Какая из ссыл ок является абсолют ной?
8. Какая из ссыл ок является отн оси тель ной?
9. Какая из ссыл ок является смешанной ?
10. В ячейке Н5 эл ектронной таб лицы записана формула =В5* V 5. Какая
формула бу дет получена из нее при к опировании в ячейку Н7:
б) = B 5* V 5
г) =$ B 5* V 5
11. В ячейке Н5 эл ектронной таблицы записана форму ла =$ B$5*V 5. Кака я
формула бу дет получена из нее при к опировании в ячейку Н7:
12. В ячейке Н5 э лектронной таблицы записана формул а =$ B $5*5. Какая
формула бу дет получена из нее при коп ировании в ячейку Н7:
13. Упорядоч ивание значений диа пазона ячеек в опре деленной
последовательн ости называют.
а) форматирова ние
б) фильтрация
в) группиров ка
г) сортировка
14. В кругл ых скобках после функц ии указывается:
а) уникальное имя функции
б) список аргу ментов
в) знака равенства
15. Выберите из нижеперечисленны х операторов, тот, к оторый не является
оператором сравнения:
16. Какая из ни жеперечисленн ых логических фу нкций не имеет аргу ментов:
17. Выражени е в ячейке А1 имеет з начение ИСТИНА . В ячейке А2 на ходится
функция: =ЕСЛИ (А1=ИСТИНА();»Прохо дите»;»Стоп»). Какое зн ачение
будет выведен о в А2?
а) «Проходите»
18. Какая форму ла возвращает значе ние 10, если значение в ячейке А1
больше 3, а в прот ивном случае – 20
а) =ЕСЛИ(А1>3; 20;10)
б) =ЕСЛИ(А1< 3;20;10)
в) =ЕСЛИ(А 1>3;10;20)
г) =ЕСЛИ(А1<3 ;10;20)
19. В ячейке А2 находится логическое в ыражение: =ЕСЛИ ( А1>=4;»Зачет
сдал»;»Зачет не с дал»). Какое число находится в ячейке А 1, если в ячейке А2
было выведе но «Зачет не сдал» :
20. Ячейка возв ращает текст «Прошел», если ученик имеет средний балл
более 4 (ячейка А 2), и пропуск занятий меньше 3 (ячейка А3). Фо рмула
примет вид:
а) =ЕСЛИ(ИЛИ (А2>4;А3<3);"Прошел" ;"Не прошел")
б) =ЕСЛИ(И(А 2>4;А3<3);"Прошел" ;"Не прошел")
в) =ЕСЛИ(И (А2>4;А3<3);"Не прошел";"П рошел")
г) =ЕСЛИ(И(А 3>3;А2<4);"Прошел" ;"Не прошел")
Для скачивания поделитесь материалом в соцсетях
После того как вы поделитесь материалом внизу появится ссылка для скачивания.
Получить код —>
Информатика — еще материалы к урокам:
- Тест «Основы работы с компьютером» 5 класс
- Тест «Информация и человек» 7 класс
- Тест «Устройство ПК»
- Тест «Объекты и системы» 6 класс
- Тест «Понятие языка разметки гипертекста» 11 класс
- Презентация «Компьютерные сети. Адресация компьютеров с сети» 9 класс
Предметы
Алгебра
Английский язык
Биология
География
Геометрия
ИЗО
Информатика
История
Литература
Математика
Музыка
МХК
Начальная школа
ОБЖ
Обществознание
Окружающий мир
ОРКСЭ
Педагогика
Русский язык
Технология
Физика
Физкультура
Химия
Экология
Похожие материалы
- 9-01-2018, 01:48 Проверочная работа «Логические функции и схемы – основа элементной
- 9-01-2018, 01:07 Презентация «Логические функции в Calc»
- 29-08-2016, 11:22 Самостоятельная работа «Встроенные математические и логические
- 29-08-2016, 11:21 Практическая работа «Встроенные математические и логические функции в
- 29-08-2016, 11:21 Конспект урока «Встроенные математические и логические функции в
- 18-08-2016, 19:03 Презентация «Таблицы истинности. Логические функции, выражения и их
- 17-08-2016, 10:00 Конспект урока «Логические функции» 8 класс
- 20-06-2016, 17:48 Лабораторно-практическая работа «Логические функции MS Excel» 9 класс
Логические выражения и операторы
Часто в реальной жизни мы соглашаемся с каким-либо утверждением или отрицаем его. Например, если вам скажут, что сумма чисел 3 и 5 больше 7, вы согласитесь, скажете: «Да, это правда». Если же кто-то будет утверждать, что сумма трех и пяти меньше семи, то вы расцените такое утверждение как ложное.
Подобные фразы предполагают только два возможных ответа – либо «да», когда выражение оценивается как правда/истина, либо «нет», когда утверждение оценивается как ошибочное/ложное. В программировании и математике если результатом вычисления выражения может быть лишь истина или ложь, то такое выражение называется логическим.
Например, выражение 4 > 5 является логическим, так как его результатом является либо правда, либо ложь. Выражение 4 + 5 не является логическим, так как результатом его выполнения является число.
На позапрошлом уроке мы познакомились с тремя типами данных – целыми и вещественными числами, а также строками. Сегодня введем четвертый – логический тип данных (тип bool ). Его также называют булевым. У этого типа всего два возможных значения: True (правда) и False (ложь).
>>> a = True >>> type(a) >>> b = False >>> type(b)
Здесь переменной a было присвоено значение True , после чего с помощью встроенной в Python функции type() проверен ее тип. Интерпретатор сообщил, что это переменная класса bool . Понятия «класс» и «тип данных» в данном случае одно и то же. Переменная b также связана с булевым значением.
В программировании False обычно приравнивают к нулю, а True – к единице. Чтобы в этом убедиться, можно преобразовать булево значение к целочисленному типу:
>>> int(True) 1 >>> int(False) 0
Возможно и обратное. Можно преобразовать какое-либо значение к булевому типу:
>>> bool(3.4) True >>> bool(-150) True >>> bool(0) False >>> bool(' ') True >>> bool('') False
И здесь работает правило: всё, что не 0 и не пустота, является правдой.
Логические операторы
Говоря на естественном языке (например, русском) мы обозначаем сравнения словами «равно», «больше», «меньше». В языках программирования используются специальные знаки, подобные тем, которые используются в математике: > (больше), < (меньше), >= (больше или равно),
Не путайте операцию присваивания значения переменной, обозначаемую в языке Python одиночным знаком «равно», и операцию сравнения (два знака «равно»). Присваивание и сравнение – разные операции.
>>> a = 10 >>> b = 5 >>> a + b > 14 True >>> a < 14 - b False >>> a >> a != b True >>> a == b False >>> c = a == b >>> a, b, c (10, 5, False)
В данном примере выражение c = a == b состоит из двух подвыражений. Сначала происходит сравнение ( == ) переменных a и b . После этого результат логической операции присваивается переменной c . Выражение a, b, c просто выводит значения переменных на экран.
Сложные логические выражения
Логические выражения типа kbyte >= 1023 являются простыми, так как в них выполняется только одна логическая операция. Однако, на практике нередко возникает необходимость в более сложных выражениях. Может понадобиться получить ответа «Да» или «Нет» в зависимости от результата выполнения двух простых выражений. Например, «на улице идет снег или дождь», «переменная news больше 12 и меньше 20».
В таких случаях используются специальные операторы, объединяющие два и более простых логических выражения. Широко используются два оператора – так называемые логические И (and) и ИЛИ (or).
Чтобы получить True при использовании оператора and , необходимо, чтобы результаты обоих простых выражений, которые связывает данный оператор, были истинными. Если хотя бы в одном случае результатом будет False , то и все сложное выражение будет ложным.
Чтобы получить True при использовании оператора or , необходимо, чтобы результат хотя бы одного простого выражения, входящего в состав сложного, был истинным. В случае оператора or сложное выражение становится ложным лишь тогда, когда ложны оба составляющие его простые выражения.
Допустим, переменной x было присвоено значение 8 ( x = 8 ), переменной y присвоили 13 ( y = 13 ). Логическое выражение y < 15 and x >8 будет выполняться следующим образом. Сначала выполнится выражение y < 15 . Его результатом будет True . Затем выполнится выражение x >8 . Его результатом будет False . Далее выражение сведется к True and False , что вернет False .
>>> x = 8 >>> y = 13 >>> y < 15 and x >8 False
В случае с оператором or второе простое выражение проверяется, если первое вернуло ложь, и не проверяется, если уже первое вернуло истину. Так как для истинности всего выражения достаточно единственного True , неважно по какую сторону от or оно стоит.
>>> y < 15 or x >8 True
В языке Python есть еще унарный логический оператор not , то есть отрицание. Он превращает правду в ложь, а ложь в правду. Унарный он потому, что применяется к одному выражению, стоящему после него, а не справа и слева от него как в случае бинарных and и or .
>>> not y < 15 False
>>> a = 5 >>> b = 0 >>> not a False >>> not b True
Число 5 трактуется как истина, отрицание истины дает ложь. Ноль приравнивается к False . Отрицание False дает True .
Практическая работа
- Присвойте двум переменным любые числовые значения.
- Используя переменные из п. 1, с помощью оператора and составьте два сложных логических выражения, одно из которых дает истину, другое – ложь.
- Аналогично выполните п. 2, но уже с оператором or .
- Попробуйте использовать в логических выражениях переменные строкового типа. Объясните результат.
- Напишите программу, которая запрашивала бы у пользователя два числа и выводила бы True или False в зависимости от того, больше первое число второго или нет.
Примеры решения и дополнительные уроки в pdf-версии курса
X Скрыть Наверх
Python. Введение в программирование
3-й семестр / Организация ЭВМиС; Орлов С.А., Цилькер Б.Я
П риложение Б Логические основы вычислительных машин Теоретическим фундаментом цифровой техники является алгебра логики , или булева алгебра , называемая так по имени ее основоположника Джорджа Буля, английского математика и логика середины XIX века. В алгебре логики переменная может принимать одно из двух значений: True (истинно) и False (ложно). Эти значения в цифровой технике принято рассматривать как логическую «1» (True) и логический «0» (False), или как двоичные числа 1 и 0, и физически представлять присутствием или отсутствием некоторого сигнала. Логические функции Функция f ( x 1 , x 2 , …, x n ), зависящая от n переменных, называется функцией алгебры логики (ФАЛ), если сама функция и любой из ее аргументов могут принимать значения только из множества <0, 1>. Другие названия ФАЛ: логическая , булева или переключательная функция. Совокупность значений аргументов функции алгебры логики называется набором , или точкой, и обозначается < x 1 , x 2 , …, x n >. Число возможных наборов из n аргументов равно 2 n . Аргументы булевой функции иногда называют булевыми. Для описания логических функций используют один из нижеперечисленных способов. Словесный способ. Здесь все случаи, при которых функция принимает значения 0 или 1, описываются словесно. Так, функцию «ИЛИ» со многими аргументами можно описать следующим образом: функция принимает значение 1, если хотя бы один из аргументов принимает значение 1, иначе значение функции равно 0. Табличный способ. Булева функция f ( x 1 . x n ) задается в виде таблицы истинности (соответствия). В левой части таблицы истинности записываются все возможные n -разрядные двоичные комбинации аргументов (табл. Б.1, а ), а в
| 612 | Приложение Б. Логические основы вычислительных машин |
правой — значения функции на этих наборах. Таблица истинности содержит 2 n строк (по числу наборов аргументов), n столбцов по числу аргументов и один столбец значений функции. Иногда вместо двоичных наборов аргументов в таблице истинности указывают их десятичные эквиваленты (табл. Б.1, б ). Таблица Б.1. Варианты представления таблицы истинности
| x 1 | x 2 | x 3 | f | Номер набора | f |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 2 | 0 |
| 0 | 1 | 1 | 0 | 3 | 0 |
| 1 | 0 | 0 | 1 | 4 | 1 |
| 1 | 0 | 1 | 1 | 5 | 1 |
| 1 | 1 | 0 | 0 | 6 | 0 |
| 1 | 1 | 1 | 1 | 7 | 1 |
| а | б |
Числовой способ. Функция задается в виде последовательности десятичных эквивалентов тех наборов аргументов, на которых функция принимает значение 1. Например, двоичные наборы 010 и 101 имеют десятичные номера 2 и 5 соответственно. При таком подходе логическая функция трех аргументов, представленная в табл. Б.1, может быть записана в виде f (1,4,5,7) = 1. Та же булева функция может быть задана и по нулевым значениям: f (0,2,3,6) = 0. Аналитический способ. Предполагает описание ФАЛ в виде алгебраического выражения, получаемого путем применения к аргументам операций булевой алгебры. Способ получения такого описания булевой функции будет рассмотрен в последующих разделах.
Рис. Б.1. Таблица истинности и эквивалентная ей карта Карно
| Логические функции | 613 |
Координатный способ. При этом способе задания таблица истинности заменяется координатной картой состояний, известной под названием карты Карно. Такая карта содержит 2 n клеток по числу возможных наборов из n переменных. Аргументы функции разбиваются на две группы так, что одна группа определяет координаты столбца, а другая — координаты строки, то есть каждой строке таблицы истинности (каждому набору аргументов) соответствует уникальная клетка карты. Внутри клетки записывается значение функции на данном наборе (рис. Б.1). Графический , или геометрический способ. Булева функция f ( x 1 . x n ) задается с помощью n -мерного куба, поскольку в геометрическом смысле каждый двоичный набор x 1 , x 2 ,…, x n есть n -мерный вектор, определяющий точку n -мерного пространства. По этой причине любой набор переменных в графическом представлении булевых функций принято называть вектором. Переменные куба называют координатами. Количество переменных в кубе определяет его мерность (3-мерный, . n -мерный). Рис. Б.2. Геометрическое представление булевой функции Множество наборов, на которых определена функция n переменных, представляется вершинами n -мерного куба. Отметив точками те вершины куба, в которых функция принимает единичное (либо нулевое) значение, получаем геометрическое представление функции. Так, булева функция, приведенная в табл. Б.1, геометрически может быть представлена 3-мерным кубом (рис. Б.2). Помимо перечисленных форм, иногда используются менее распространенные способы описания ФАЛ: комбинационной схемой, составленной из логических элементов; переключательной схемой; диаграммой Венна; диаграммой двоичного решения и т. д. Булеву функцию, определенную на всех возможных наборах переменных, называют полностью определенной . Пример такой функции был показан в табл. Б.1. Булеву функцию n переменных называют частично определенной , или просто частичной , если она определена не на всех двоичных наборах длины n . Наборы, на которых значение ФАЛ не определено, в таблице истинности обычно помечают каким-либо символом, например звездочкой (табл. Б.2).
| 614 | Приложение Б. Логические основы вычислительных машин | |||||
| Таблица Б.2. Таблица истинности для частично определенной булевой функции | ||||||
| x 1 | x 2 | x 3 | f | |||
| 0 | 0 | 0 | 0 | |||
| 0 | 0 | 1 | 1 | |||
| 0 | 1 | 0 | ||||
| 0 | 1 | 1 | 0 | |||
| 1 | 0 | 0 | 1 | |||
| 1 | 0 | 1 | ||||
| 1 | 1 | 0 | 0 | |||
| 1 | 1 | 1 | ||||
Элементарные функции алгебры логики В случае n переменных возможно не более 2 2 n различных булевых функций. Элементарные функции одной переменной В случае единственной переменной возможны 4 функции f 10 i ( x ), показанные в табл. Б.3 и поясненные в табл. Б.4. При аналитическом описании ФАЛ наибольший интерес представляет функция логического отрицания f 102 , согласно которой результат равен True , если значение аргумента было False , и наоборот. Таблица Б.3. Логические функции одной переменной
| Переменная | Логические функции | |||
| x | f 100 | f 101 | f 102 | f 103 |
| 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| Таблица Б.4. Описание логических функций одной переменной | ||||
| Функция | Название | Обозначение | ||
| f 100 | Константа нуля | f 100 ( x ) = 0 | ||
| f 101 | Повторение x | f 101 ( x ) = x | ||
| f 102 | Логическое отрицание, инверсия (от лат. | |||
| f 102 ( x ) = x ; | ||||
| inversio – переворачиваю), «НЕ» | ||||
| f 102 ( x ) = ← x | ||||
| f 103 | Константа единицы | f 103 ( x ) = 1 | ||
Элементарные функции двух переменных
Для двух переменных можно сформировать 16 (и только 16) логических функций (табл. Б.5, Б.6).
| Элементарные функции алгебры логики | 615 | ||||||||||||||||
| Таблица Б.5. Логические функции двух переменных | |||||||||||||||||
| Аргументы | Логические функции | ||||||||||||||||
| x 1 | x 2 | f 200 | f 201 | f 202 | f 203 | f 204 | f 205 | f 206 | f 207 | f 208 | f 209 | f 210 | f 211 | f 212 | f 213 | f 214 | f 215 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
Функции двух переменных, рассмотренные в табл. Б.6, играют важную роль в алгебре логики и могут быть названы элементарными.
| Таблица Б.6. Описание логических функций двух переменных 1 | ||||||||||||||||||||||||||||||
| Функция | Название | Обозначение | ||||||||||||||||||||||||||||
| f 200 | Константа 0 | f 200 | ( x 1 | , x 2 ) = 0 или False | ||||||||||||||||||||||||||
| f 201 | Логическое умножение, конъ- | f 201 | ( x 1 , x 2 ) = x 1 x 2 | или x 1 x 2 | ||||||||||||||||||||||||||
| юнкция, «И» | ||||||||||||||||||||||||||||||
| или | x 1 & x 2 | или x 1 and x 2 | ||||||||||||||||||||||||||||
| f 202 | Запрет по x 2 | f 202 | ( x 1 | , x 2 ) = x 1 ∆ x 2 | или x 1 | |||||||||||||||||||||||||
| x 2 | ||||||||||||||||||||||||||||||
| f 203 | Переменная x 1 1 | f 203 ( x 1 | , x 2 ) = x 1 | |||||||||||||||||||||||||||
| f 204 | Запрет по x 1 | |||||||||||||||||||||||||||||
| f 204 | ( x 1 | , x 2 ) = x 2 ∆ x 1 или x 1 x 2 | ||||||||||||||||||||||||||||
| f 205 | Переменная x 2 | f 205 ( x 1 | , x 2 ) = x 2 | |||||||||||||||||||||||||||
| f 206 | Сложение по модулю 2, от- | f | 206 | ( x , x ) = x x | или x | xor x | ||||||||||||||||||||||||
| рицание эквивалентности, | 1 | 2 | 1 | 2 | 1 | 2 | ||||||||||||||||||||||||
| «Исключающее ИЛИ» | или ( | x 1 | x 2 ) ( x 1 | x 2 | ) | |||||||||||||||||||||||||
| f 207 | Логическое сложение, дизъ- | f 207 | ( x 1 , x 2 ) = x 1 x 2 или x 1 @ x 2 | |||||||||||||||||||||||||||
| юнкция, «ИЛИ» | ||||||||||||||||||||||||||||||
| или x 1 + x 2 | или x 1 or x 2 | |||||||||||||||||||||||||||||
| f 208 | Функция Пирса (Вебба), | |||||||||||||||||||||||||||||
| f 208 | ( x 1 | , x 2 ) = x 1 ↓ x 2 | или x 1 x 2 | |||||||||||||||||||||||||||
| «ИЛИ-НЕ» | ||||||||||||||||||||||||||||||
| или | x 1 | x 2 | ||||||||||||||||||||||||||||
| f 209 | Логическая равнозначность, | f | 209 | ( x , x | ) = x | ~ x | 2 | или x | ↔ x | |||||||||||||||||||||
| эквиваленция | 1 | 2 | 1 | 1 | 2 | |||||||||||||||||||||||||
| или ( | ) ( x 1 x 2 ) | |||||||||||||||||||||||||||||
| x 1 | x 2 | |||||||||||||||||||||||||||||
| или | ||||||||||||||||||||||||||||||
| x 1 x 2 | ||||||||||||||||||||||||||||||
| f 210 | Отрицание x 1 | f | ( x , x | ) = | ||||||||||||||||||||||||||
| 210 | 2 | x | 2 | |||||||||||||||||||||||||||
| 1 | ||||||||||||||||||||||||||||||
продолжение 1 Если значение переменной в функции не влияет на значение функции, как в случае переменной x 2 в функции f 203 , то такая переменная называется фиктивной (несущественной).
| 616 | Приложение Б. Логические основы вычислительных машин | ||||||||||||||||
| Таблица Б.6 ( продолжение ) | |||||||||||||||||
| Функция | Название | Обозначение | |||||||||||||||
| f 211 | Правая импликация | ||||||||||||||||
| f 211 | ( x 1 , x 2 ) = x 1 x 2 | 8; 8 | x 2 | → x 1 | |||||||||||||
| f 212 | Отрицание x 2 | f 212 ( x 1 , x 2 ) = | |||||||||||||||
| x 1 | |||||||||||||||||
| f 213 | Левая импликация | ||||||||||||||||
| f 213 | ( x 1 | , x 2 ) = x 1 x 2 | 8; 8 | x 1 | → x 2 | ||||||||||||
| f 214 | Функция Шеффера, «И НЕ» | ||||||||||||||||
| f 214 | ( x 1 | , x 2 ) = x 1 | x 2 8; 8 | x 1 | x 2 | ||||||||||||
| 8; 8 | |||||||||||||||||
| x 1 | x 2 | ||||||||||||||||
| f 215 | Константа 1 | f 215 ( x 1 | , x 2 ) = 1 8; 8 | True | |||||||||||||
Рассмотренные элементарные функции позволяют строить более сложные булевы функции с помощью операции суперпозиции, заключающейся в подстановке в функцию новых функций вместо аргументов. Так, путем замены в функции f 1 ( x 1 , x 2 ) аргументов x 1 и x 2 на функции f 2 = x 6 и f 3 ( x 5 , x 7 ) получаем функцию f 1 ( x 6 , f 3 ( x 5 , x 7 )) . Суперпозиция функций двух аргументов дает возможность стро- ить функции любого числа аргументов. Суперпозиция булевых функций представляется в виде логических формул, причем следует учитывать, что одна и та же функция может быть представлена разными формулами, среди которых имеется и наиболее простая. Нахождение такой формулы составляет предмет минимизации ФАЛ, рассматриваемой ниже. Правила алгебры логики Как и любая другая математическая дисциплина, булева алгебра базируется на определенном своде правил, представленных в виде аксиом, теорем и законов (тождеств). Правила эти определяются для двух возможных логических значений «1» (True) и «0» (False), а также трех базовых логических операций: «НЕ», «И» и «ИЛИ», в силу чего основные правила алгебры логики формулируются, главным образом, для этих операций и их сочетаний. Базовые логические операции перечислены в порядке понижения их приоритетности. Учет приоритетности операций позволяет сократить число скобок при записи логических выражений. Аксиомы алгебры логики Как известно, аксиомами в математике принято называть предположения, не требующие доказательств. 1. Аксиомы конъюнкции 0 0 = 0; 0 1 = 0; 1 0 = 0; 1 1 = 1. 2. Аксиомы дизъюнкции 0 0 = 0; 0 1 = 1; 1 0 = 1; 1 1 = 1.
| Правила алгебры логики | 617 |
3. Аксиомы отрицания если x = 0, то x = 1 ; если x = 1, то x = 0 . Теоремы алгебры логики Для доказательства теорем булевой алгебры используется простая подстановка значений булевых переменных. Это обусловлено тем, что переменные могут принимать только два значения — «0» и «1». 4. Теоремы исключения констант x 1 = 1; x 0 = x ; x 1 = x ; x 0 = 0. 5. Теоремы идемпотентности (тавтологии, повторения) x x = x ; x x = x . Для n переменных: x x … x = x ; x x … x = x . Повторное применение не дает ничего нового. 6. Теорема противоречия x x = 0 . Невозможно, чтобы противоречащие высказывания были одновременно истинными. 7. Теорема «исключенного третьего» x x = 1. Из двух противоречивых высказываний об одном и том же предмете одно всегда истинно, а второе — ложно, третьего не дано. 8. Теорема двойного отрицания (инволюции) x = x . Двойное отрицание отменяет инверсию. Законы алгебры логики Излагаемые ниже правила обычно называют законами, или тождествами булевой алгебры. 9. Ассоциативный (сочетательный) закон x 1 ( x 2 x 3 ) = ( x 1 x 2 ) x 3 ; x 1 ( x 2 x 3 ) = ( x 1 x 2 ) x 3 . При одинаковых знаках скобки можно ставить произвольно или вообще опускать. 10. Коммутативный (переместительный) закон x 1 x 2 = x 2 x 1 ; x 1 x 2 = x 2 x 1 . Результат операции над высказываниями не зависит от того, в каком порядке берутся эти высказывания.
| 618 | Приложение Б. Логические основы вычислительных машин |
11. Дистрибутивный (распределительный) закон ( x 1 x 2 ) x 3 = ( x 1 x 3 ) ( x 2 x 3 ); ( x 1 x 2 ) x 3 = ( x 1 x 3 ) ( x 2 x 3 ). Закон определяет правило выноса общего высказывания за скобку. 12. Законы де Моргана (законы общей инверсии или дуальности)
x 1 x 2 = x 1 x 2 x 1 x 2 = x 1 x 2 Расширенный закон де Моргана: x 1 x 2 . x n x 1 x 2 . x 2
; x 1 x 2 = x 1 x 2 ; ; x 1 x 2 = x 1 x 2 . = x 1 x 2 . x n ; = x 1 x 2 . x n .
Законы де Моргана можно рассматривать как частный случай теоремы Шеннона, которая утверждает, что инверсия любой функции в алгебре логики получается путем замены каждой переменной ее инверсией и одновременно взаимной заменой символов конъюнкции и дизъюнкции. 13. Закон поглощения (элиминации) x 1 ( x 1 x 2 ) = x 1 ; x 1 ( x 1 x 2 ) = x 1 . 14. Закон склеивания (исключения) ( x 1 x 2 ) ( x 1 x 2 ) = x 1 ; ( x 1 x 2 ) ( x 1 x 2 ) = x 1 . Справедливость приведенных законов можно доказать табличным способом: выписать все наборы значений x 1 и x 2 , вычислить на них значения левой и правой частей доказываемого выражения и убедиться, что результирующие столбцы совпадут. В дальнейшем для облегчения восприятия приводимых логических выражений знак конъюнкции будем опускать и записывать логическое произведение как обычное, то есть выражение типа x 1 € € x 2 € € x 3 будем писать в виде x 1 € x 2 € x 3 . В ряде случаев, чтобы избежать слияния знаков отрицания, между переменными может вставлять- ся точка, например x 1 x 2 x 3 . Дополнительные тождества алгебры логики В данном разделе без доказательства приводятся некоторые дополнительные тождества алгебры логики, которые могут оказаться полезными при минимизации ФАЛ. Некоторые из них представляют собой лишь иную форму записи ранее рассмотренных тождеств. x 1 ( x 1 x 2 ) = x 1 x 2 ; x 1 ( x 1 x 2 ) = x 1 x 2 ;
| Аналитическое представление булевых функций | 619 |
x 1 x 2 x 1 x 3 x 2 x 3 = x 1 x 2 x 1 x 3 ; x 1 ( x 1 x 2 ) = x 1 x 2 ; ( x 1 x 2 )( x 1 x 3 ) = x 1 x 3 x 1 x 2 ; ( x 1 x 2 )( x 1 x 3 )( x 2 x 3 ) = ( x 1 x 2 )( x 1 x 3 ) . Логический базис Любую булеву функцию с произвольным количеством аргументов можно построить через суперпозицию элементарных логических функций одной и двух переменных. Набор простейших функций, с помощью которого можно выразить любые другие, сколь угодно сложные логические функции, называется функционально полным набором , или логическим базисом . На практике в качестве базисов обычно используются следующие системы логических функций: «НЕ», «И», «ИЛИ» — булев базис;«И-НЕ» — универсальный базис Шеффера; «ИЛИ-НЕ» — универсальный базис Пирса;«Исключающее ИЛИ», «И», «Константа 1» — базис Жегалкина;«Запрет по X 2 », «1». Логический базис называется минимальным , если удаление хотя бы одной из входящих в него функций превращает этот набор в функционально неполный. Логический базис «И», «ИЛИ», «НЕ» не является минимальным, так как с помощью формул де Моргана можно исключить из логических выражений либо функцию «И», либо функцию «ИЛИ». В результате получаются минимальные базисы: «И», «НЕ» и «ИЛИ», «НЕ». Некоторые функции сами по себе представляют собой минимальный логический базис. К таким, например, относятся функции «И-НЕ» и «ИЛИ-НЕ». Чаще всего для записи логических выражений и их последующего преобразования используется базис «И», «ИЛИ», «НЕ». Аналитическое представление булевых функций В качестве исходного описания сложных логических функций обычно используется таблица истинности, однако упрощение функций выгоднее производить в аналитической форме. При аналитической записи ФАЛ представляется либо в виде логической суммы элементарных логических произведений (дизъюнкции элементарных конъюнкций), либо в виде логического произведения элементарных логических сумм (конъюнкции элементарных дизъюнкций). Первая форма записи носит название дизъюнктивной нормальной формы (ДНФ), вторая — конъюнктивной нормальной формы (КНФ).
Сначала определим основные понятия и терминологию, используемые при аналитическом представлении ФАЛ.
| 620 | Приложение Б. Логические основы вычислительных машин |
Элементарной конъюнкцией (элементарным логическим произведением) называют логическое произведение любого количества переменных (аргументов), взятых с отрицанием или без, но каждый из аргументов встречается в этом произведении лишь однократно. Элементарная конъюнкция, включающая все без исключения аргументы ФАЛ, носит название полной элементарной конъюнкции . Дизъюнктивная нормальная форма (ДНФ) — это логическая сумма элементарных логических произведений (дизъюнкция элементарных конъюнкций). Термин «нормальная» означает, что в выражении отсутствуют групповые инверсии, то есть общий знак отрицания над несколькими переменными сразу, например, x 1 x 2 . Примером ДНФ может служить выражение x 1 x 2 x 1 x 2 x 3 x 1 x 2 x 3 . Минтерм (единичный набор функции) — это логическое произведение всех переменных, взятых с отрицанием или без (полная элементарная конъюнкция), соответствующее набору аргументов, на которых функция принимает значение «1». Каждый минтерм соответствует одной строке таблице истинности, причем только такой, где значение функции равно 1 (True). Множество всех минтермов образует единичное множество функции . Совершенной дизъюнктивной нормальной формой (СДНФ) называется ДНФ, состоящая из всех минтермов булевой функции. Для получения СДНФ на основе таблицы истинности необходимо: каждый из входных наборов, на которых булева функция принимает значение «1», представить в виде элементарного произведения (конъюнкции), причем если переменная равна 0, то она входит в конъюнкцию с инверсией, а если 1 — то без инверсии; полученные элементарные логические произведения объединить знаками логического сложения (дизъюнкции). Число элементарных произведений (минтермов) в СДНФ равно числу строк таб лицы истинности, на которых функция имеет значение «1». Для получения минтерма в него нужно включить все аргументы, причем те из них, которые имеют в данном наборе нулевое значение, входят в минтерм со знаком отрицания. Так, таблице истинности
| x 1 | x 2 | f |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
отвечает совершенная дизъюнктивная нормальная форма f = x 1 x 2 x 1 x 2 x 1 x 2 . Элементарная дизъюнкция (элементарная логическая сумма) — это логическая сумма (дизъюнкция) любого числа переменных, взятых с отрицанием или без, причем каждый отдельный аргумент встречается лишь однократно. Элементарная дизъюнкция, включающая все без исключения аргументы ФАЛ, называется полной элементарной дизъюнкцией .
Логика. Основные сведения.
Утверждения (они же: высказывания) об объектах окружающего мира строятся из элементарных высказываний. Такие высказывания утверждают что-то о свойствах объекта или об отношениях между объектами (чаще всего – между двумя объектами).
- Забор красный. Здесь забор – объект, а красный описывает его свойство. «красный» (иногда говорят – свойство «быть красным»). Имеется в виду конкретный забор, а не забор вообще! В русском языке свойства часто (но не всегда) выражаются прилагательными.
- Коля и Петя – друзья. Здесь Коля и Петя – «объекты», а слово друзья описывает отношение между ними. Это отношение симметрично – смысл сказанного не поменяется, если написать «Петя и Коля – друзья». Здесь, как и во всех элементарных высказываниях, имеются в виду конкретные люди.
- Коля старше, чем Петя. Здесь отношение описывается словами «старше, чем». Это отношение не является симметричным.
Высказывание может быть истинным (верным) или ложным (неверным). Например, Коля может на самом деле быть старше, чем Петя (тогда высказывание 3 истинно). А, может быть, Коля младше Пети, или они одного возраста. Тогда это высказывание ложно.
1.2. Объекты, свойства и отношения в математике.
В математике мы имеем дело с математическими объектами, их свойствами и отношениями. Примеры математических объектов: числа: натуральные, целые, рациональные (они же - обыкновенные дроби), вещественные; точки, прямые, множества. С числами, точками и прямыми вы познакомились на уроках математики. Про множества коротко написано здесь.
Вот примеры свойств, отношений и высказываний для целых чисел (при описании свойств и отношений вместо чисел стоят многоточия…) .
Свойства: … - четное; … - нечетное, … - положительное.
Примеры высказываний: (1) 4 – четное. (2) 4 – нечетное. (3) 4 – положительное. Здесь первое и третье высказывание истинны, а второе – ложно.
Отношение: …больше, чем …; … меньше, чем…; … делится на … .
Примеры высказываний: (1) 4 больше, чем 2. (2) 4 меньше, чем 2. (3) 4 делится на 2. Здесь тоже первое и третье высказывание истинны, а второе – ложно.
В математике отношения часто записываются специальными знаками. Например, 6 < 3.
Замечание . Вместо «явного» обозначения, например, чисел в высказываниях можно использовать и выражения, значениями которых являются числа. Пример:
1.3. Утверждения всеобщности.
В школьной (и не только �� ) математике в элементарных высказываниях часто используются не только «имена» объектов (числа, множества и др.), но и переменные. Пример:
a+b = b+a
Здесь имеется в виду вот что. Для любых чисел, если их подставить вместо a и b, получится истинное высказывание. То есть, истинны все указанные ниже высказывания и еще бесконечно много подобных им высказываний:
27 + 12 = 12 + 27 (вместо a подставили 27, вместо b подставили 12)
2 + 5 = 5 + 2 (вместо a подставили 2, вместо b подставили 5)
5 + 2 = 2 + 5 (вместо a подставили 5, вместо b подставили 2)
5 + 5 = 5 + 5 (вместо a подставили 5, вместо b тоже подставили 5)
Истинность утверждений о всеобщности нельзя проверить непосредственно! Их нужно доказывать (или принимать в качестве аксиом).
2. Логические значения, логические связки и логические высказывания
2.1. Составные высказывания
Из элементарных высказываний можно строить более сложные (составные) высказывания, используя связки И, ИЛИ, НЕ.
Примеры. Забор красный И забор деревянный.
Коля старше, чем Петя ИЛИ Коля старше, чем Федя
Забор НЕ красный.
Смысл этих высказываний понятен.
Высказывание с И содержит два элементарных высказывания. Составное высказывание с И истинно тогда и только тогда, когда истинны оба эти элементарные высказывания. Если хоть одно из них ложно, - составное высказывание ложно.
Высказывание с ИЛИ тоже содержит два элементарных высказывания. Составное высказывание с ИЛИ истинно тогда и только тогда, когда истинно хотя бы одно из этих элементарных высказываний. Если оба эти высказывания ложны, - составное высказывание ложно.
Высказывание с НЕ содержит одно элементарное высказывание (в русском языке НЕ часто ставится в середину этого высказывания). Составное высказывание с НЕ истинно, если исходное элементарное высказывание ложно и, наоборот, если исходное высказывание истинно, то составное высказывание с НЕ ложно.
Составные высказывания можно строить не только из элементарных высказываний, но и из других составных высказываний. В этом построение составных высказываний похоже на построение алгебраических выражений. Например, понятно, что означает такое высказывание (хотя оно написано не на русском языке, а с использованием скобок : )
(Коля старше, чем Петя ИЛИ Коля старше, чем Федя) И (Коля НЕ старше, чем Ваня)
Здесь 3 элементарных высказывания.
2.2. Логические значения. Логические операции.
Мы уже знаем, что каждому высказыванию можно приписать одно из двух логических значений – истина (часто обозначается: 1) или ложь (часто обозначается: 0). Слова И, ИЛИ, НЕ задают операции над логическими значениями (логические операции). Действительно, например, составное высказывание с И истинно тогда и только тогда, когда истинны оба его элементарные высказывания. Если хоть одно из них ложно, - составное высказывание ложно. Здесь нам не важно, каковы были исходные высказывания. Истинность составного высказывания зависит только от логического (иногда говорят - истинностного) значения исходных высказываний.
Так как логических значений всего два, то эти операции можно описать таблицами.
У операций И, ИЛИ, НЕ есть «научные» названия (даже несколько для каждой операции �� и специальные обозначения (в примерах A, B обозначают какие-то конкретные логические значения):
НЕ: отрицание, инверсия. Обозначение: ¬ (например, ¬А);
И: конъюнкция, логическое умножение.
Обозначается /\ (например, А /\ В) либо & (например, А & В);
ИЛИ: дизъюнкция, логическое сложение.
Обозначается \/ (например, А \/ В).
В математике используются и другие логические операции.
Каждая логическая операция может быть задана своей таблицей. Вот еще два примера логических операций:
1) следование (импликация); обозначается → (например, А → В). Выражение А → В истинно если A ложно ИЛИ B истинно. То есть, А → В означает то же самое, что и (¬А) \/ В. См. таб. 4.
2) тождество (эквивалетность); обозначается ≡ (например, A ≡ B). Выражение A ≡ B истинно тогда и только тогда, когда значения A и B совпадают (либо они оба истинны, либо они оба ложны). См. таб. 5.
2.3. Логические выражения. Таблицы истинности.
Логические операции играют для логических значений ту же роль, что и арифметические операции для чисел. Аналогично построению алгебраических выражений, с помощью логических операций можно строить логические выражения. Как и алгебраические выражения, логические выражения могут включать константы (логические значений 1 и 0) и переменные. Если в логическом значении есть переменные, оно задает функцию (логическую функцию; синоним: булеву функцию). Значение такой функции при заданном наборе значений аргументов вычисляется подстановкой этих значений в выражение вместо переменных.
Для каждого логического выражения можно составить таблицу истинности, которая описывает, какое значение принимает соответствующая логическая функция (синоним: принимает выражение) при каждом допустимом наборе значений переменных. Каждая строка таблицы истинности соответствует одному возможному набору аргументов логической функции. Поэтому таблица истинности для логической функции от n переменных содержит 2 n строк. В каждой строке таблицы истинности указывается набор значений переменных и значение функции, соответствующее этому набору. Вот таблицы истинности для выражений x \/ y (таблица 6), x → y (таблица 7) и (x → y) /\ (y → z) (таблица 8).
2.4. Приоритеты логических операций.
При записи логических выражений, как и при записи алгебраических выражений, иногда можно не писать скобки При этом соблюдаются следующие договоренности о старшинстве (приоритете) логических операций, первыми указаны операции, которые выполняются в первую очередь:
конъюнкция (логическое умножение),
дизъюнкция (логическое сложение),
Таким образом, ¬А \/ В \/ С \/ D означает то же, что и ((¬А) \/ В)\/ (С \/ D).
Возможна запись А \/ В \/ С вместо (А \/ В) \/ С. То же относится и к конъюнкции: возможна запись А /\ В /\ С вместо (А /\ В) /\ С.
3. Свойства логических выражений и таблиц истинности.
Приведенный ниже список НЕ претендует на полноту, но, надеемся, достаточно представителен.
3.1. Общие свойства
1) Для n логических переменных существует ровно 2 n различных наборов значений.
2) Таблица истинности для логического выражения от n переменных содержит n+1 столбец (по одному столбцу на каждую переменную + 1 столбец на значение выражения) и 2 n строк (по одной строке на каждый набор значений переменных).
1) Если хоть одно из выражений, к которым применяется дизъюнкция, истинно на некотором наборе значений переменных, то и вся дизъюнкция истинна для этого набора значений.
2) Если все выражения из некоторого списка ложны на некотором наборе значений переменных, то дизъюнкция этих выражений тоже ложна.
3) Значение дизъюнкции не зависит от порядка записи выражений, к которым она применяется.
4) При вычислении дизъюнкции выражений эти выражения можно группировать как угодно - значение дизъюнкции не изменится.
5) Пусть все выражения, к которым применяется дизъюнкция, - это различные переменные или их отрицания. Тогда существует ровно один набор значений переменных, при которых дизъюнкция ложна. Переменная в этом наборе имеет значение 1, если в дизъюнкцию она входит с отрицанием и значение 0 в противном случае.
1) Если хоть одно из выражений, к которым применяется конъюнкция, ложно на некотором наборе значений переменных, то и вся конъюнкция ложна для этого набора значений.
2) Если все выражения из некоторого списка истинны на некотором наборе значений переменных, то конъюнкция этих выражений тоже истинна.
3) Значение конъюнкции не зависит от порядка записи выражений, к которым она применяется.
4) При вычислении конъюнкции выражений эти выражения можно группировать как угодно - значение конъюнкции не изменится.
5) Пусть все выражения, к которым применяется конъюнкция, - это различные переменные или их отрицания. Тогда существует ровно один набор значений переменных, при которых конъюнкция истинна. Переменная в этом наборе имеет значение 1, если в конъюнкцию она входит без отрицания и значение 0 в противном случае.
1) Импликация A →B равносильна дизъюнкции (¬А) \/ В. Эту дизъюнкцию можно записать и так: ¬А \/ В.
2) Импликация A →B принимает значение 0 (ложь) только если A=1 и B=0. Если A=0, то импликация A→B истинна при любом значении B. Если B=1, то импликация A→B истинна при любом значении A.
1) Эквивалентность A ≡ B равносильна конъюнкции двух импликаций: A→B и B→A. Эту конъюнкцию можно записать так: (A→B)/\ (B→A)
2) Эквивалентность A ≡ B принимает значение 1 (истина) тогда и только тогда, когда значения переменных A и B одинаковы, т.е. A=B=1 или A=B=0.
Поэтому эквивалентность A ≡ B равносильна выражению (A/\B) \/ ((¬А) /\ (¬В) ).
3) Эквивалентность A ≡ B принимает значение 0 (ложь) тогда и только тогда, когда значения переменных A и B различны, т.е. A=0, а B=1 или A=1, а B=0. Поэтому эквивалентность A ≡ B равносильна выражению ¬ ( (A/\¬B) \/ (А /\¬В) )
3.6. Построение выражения с заданной таблицей истинности
Для любого множества наборов значений переменных можно построить выражение, которое истинно на всех наборах из заданного множества и только на них. Это выражение удобно записать в виде дизъюнкции конъюнкций, причем в каждой конъюнкции (а) каждый член – это простая переменная или ее отрицание и при этом (б) содержатся все переменные.
Тогда функция F может быть задана таким выражением:
Здесь первый член дизъюнкции соответствует первой строке таблицы фрагмента истинности; второй член – второй строке; третий член – третьей строке.
Таким образом, для любой таблицы истинности можно построить логическое выражение с данной таблицей истинности.
4. Эквивалентные преобразования логических выражений
4.1. Эквивалентные выражения.
Два логических выражения, содержащих переменные, называются равносильными (эквивалентными), если значения этих выражений совпадают при любых значениях переменных. Так, выражения А → В и (¬А) \/ В равносильны, а А/\В и А \/ В – нет (значения выражений разные, например, при А = 1, В = 0).
Эквивалентные выражения имеют одинаковые таблицы истинности, а у неэквивалентных выражений таблицы истинности различны.
Понятие эквивалентности для логических выражений полностью аналогично понятию эквивалентности для алгебраических выражений.
4.2. Эквивалентные (тождественные) преобразования выражений.
Выяснить, эквивалентны ли два выражения, можно сравнив их таблицы истинности. Но это не всегда удобно: построение таблицы истинности - громоздкая задача. Кроме того, часто нужно не просто проверить, эквивалентны ли два данных логических выражения, а построить для данного выражения эквивалентное ему выражение, имеющее заданный вид. Например, бывает удобно представить выражение в виде дизъюнкции или в виде импликации (см. здесь). Аналогия для алгебраических выражений: разложить на множители выражение x 2 -y 2 (ответ: (x-y)*(x+y) ).
Замена выражения на другое выражение, эквивалентное ему, называется эквивалентным (синоним: тождественным) преобразованием.
Основное правило тождественных преобразование - это правило подстановки: если в выражении A заменить подвыражение P на эквивалентное ему выражение Q, то полученное новое выражение B будет эквивалентно исходному выражению A.
Правило подстановки работает и для логических, и для алгебраических выражений.
Пример 1. Рассмотрим выражение A = (x→y)∨z . Заменим подвыражение P = x→y на эквивалентное ему по определению выражение Q = ¬x∨y. Заменяем в A выражение P выражением Q. Получим выражение B = (¬x∨y)∨z. Выражение B эквивалентно выражению A. Учитывая приоритеты выполнения логических операций, выражение B можно записать и так: ¬x∨y∨z.
4.3. Основные логические тождества.
Между решением задач на эквивалентное преобразование логических и алгебраических выражений есть существенная разница. В алгебре есть устоявшийся список тождественных преобразований выражений. В него входят формулы, связанные с определением степени и основными законами сложения и умножения (сочетательный, переместительный, распределительный), а также так называемые формулы сокращенного умножения (квадраты и кубы суммы и разности; разность квадратов, сумма и разность кубов). В курсе логики такого общепринятого списка нет.
В таблице 1 приведен набор логических тождеств (пар эквивалентных логических выражений), которые полезно знать, сдавая ЕГЭ. Это не значит, что другие элементарные тождества вам не понадобится. Мы просто надеемся, что вы сможете при необходимости вывести другие понадобившиеся тождества. Желательно уметь пользоваться этими формулами так же свободно, как, например, алгебраическими формулами сокращенного умножения. Деление формул в таблице на группы – условное и приведено лишь для удобства восприятия.
Примечание. В таблицах использована «алгебро-подобная» система обозначений логических операций. Конъюнкция (логическое умножение) и дизъюнкция (логическое сложение) обозначаются символами «·» и «+» соответственно, а отрицание – чертой сверху. Эти обозначения общеприняты среди инженеров (но не специалистов по математической логике :)) и используются в некоторых школьных учебниках, в частности, в учебниках К.Ю.Полякова и Е.А.Еремина
5. Высказывания о множествах
Логические выражения над элементарными высказываниями о множествах (высказывания вида "A=∅", "x∈A" "A⊆B" ) можно преобразовывать, используя не только общие правила преобразования логических выражений, но и свои правила, связанные со свойствами операций над множествами. Ниже U - это универсальное множество; x - его произвольный элемент, A, B, X - множества. Верны следующие утверждения.
1. Следующие высказывания эквивалентны, т.е. имеют одинаковые логические значения при любых x, A, B (это обозначено знаком ⇔)
2. Следующие высказывания эквивалентны, т.е. имеют одинаковые логические значения при любых X, A, B (это обозначено знаком ⇔)
3. (а) Пусть A ⊆ B, т.е. A - подмножество B; x - элемент универсального множества U. Тогда истинно высказывание:
(б) Пусть высказывание (x ∈ A) → (x∈ B) истинно при любом x ∈ U. Тогда A ⊆ B.
4. (а) Пусть A ⊆ B, т.е. A - подмножество B; X ⊆ U - произвольное множества. Тогда истинно высказывание:
(б) Пусть высказывание (X∩A ≠Ø ) → (X∩B ≠Ø ) истинно для любого множества X ⊆ U. Тогда A ⊆ B.
5. Следующее высказывания истинны для любых множеств A, B, X
6. Примеры эквивалентных преобразований
Первые два примера содержат доказательства свойств импликации из таблицы 1С (см. п.4).
Пример 1 . Преобразуем выражение (¬y)→ (¬x) в выражение x→ y. Имеем:
1) (¬y) ∨ (¬(¬x) ) - замена импликации дизъюнкцией
3) x → y - замена дизъюнкции импликацией
Пример 2 . Преобразуем выражение x → (y→ z) в выражение (x∧y)→ z. Имеем:
При анализе высказываний о множествах бывает удобно преобразовывать выражения к импликации, у которой и левый, и правый члены импликации не содержат. Рассмотрим такие примеры.