Никаких других формул в алгебре логики нет

7.15.

7.14.

Ответ

Ответ

Ответ

Ответ

Ответ

Ответ

Ответ

Ответ

Ответ

Ответ

Ответ

Ответ

Ответ

Ответ

Ответ

Ответ

Ответ

Ответ

Ответ

Ответ

Ответ

Ответ

Ответ

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

7.1. Используя Правило Счета, запишите первые 20 целых чисел в десятичной, двоичной, троичной, пятеричной и восьмеричной системах счисления.

7.2. Какие целые числа следуют за числами:

а) 12;	е) 18;	п) F16;
б) 1012;	ж) 78;	м) 1F16;
в) 1112;	з) 378;	н) FF16;
г) 11112;	и) 1778;	о) 9AF916;
д) 1010112;	к) 77778;	п) CDEF16?

7.3. Какие целые числа предшествуют числам:

а) 102;	е) 108;	л) 1016;
б) 10102;	ж) 208;	м)2016;
в) 10002;	з) 1008;	н) 10016;
г) 100002;	и) 1108;	о) A1016;
д) 101002;	к) 10008;	п) 100016?

7.4. Какой цифрой заканчивается четное двоичное число? Какой цифрой заканчивается нечетное двоичное число? Какими цифрами может заканчиваться четное троичное число?

7.5. Какое наибольшее десятичное число можно записать тремя цифрами:

а) в двоичной системе;

б) в восьмеричной системе;

в) в шестнадцатеричной системе?

7.6. В какой системе счисления справедливо следующее:

а) 20 + 25 = 100;

б) 22 + 44 = 110?

7.7. Десятичное число 59 эквивалентно числу 214 в некоторой другой системе счисления. Найдите основание этой системы.

7.8. Переведите числа в десятичную систему, а затем проверьте результаты, выполнив обратные переводы:

а) 10110112;	е) 5178;	л) 1F16;
б) 101101112;	ж) 10108;	м) ABC16;
в) 0111000012;	з) 12348;	н) 101016;
г) 0,10001102;	и) 0,348;	о) 0,А416;
д) 110100,112;	к) 123,418;	п) 1DE,C816.

7.9. Переведите числа из десятичной системы в двоичную, восьмеричную и шестнадцатеричную, а затем проверьте результаты, выполнив обратные переводы:

а) 125₁₀; б) 229₁₀; в) 88₁₀; г) 37,25₁₀; д) 206,125₁₀.

7.10. Переведите числа из двоичной системы в восьмеричную и шестнадцатеричную, а затем проверьте результаты, выполнив обратные переводы:

а) 1001111110111,01112;	г) 1011110011100,112;
б) 1110101011,10111012;	д) 10111,11111011112;
в) 10111001,1011001112;	е) 1100010101,110012.

7.11. Переведите в двоичную и восьмеричную системы шестнадцатеричные числа:

а) 2СE₁₆; б) 9F40₁₆; в) ABCDE₁₆; г) 1010,101₁₆; д) 1ABC,9D₁₆.

7.12. Выпишите целые числа:

а) от 101101₂ до 110000₂ в двоичной системе;

б) от 202₃ до 1000₃ в троичной системе;

в) от 14₈ до 20₈ в восьмеричной системе;

г) от 28₁₆ до 30₁₆ в шестнадцатеричной системе.

Ответ

7.13. Для десятичных чисел 47 и 79 выполните цепочку переводов из одной системы счисления в другую:

Ответ

7.14. Составьте таблицы сложения однозначных чисел в троичной и пятеричной системах счисления.

7.15. Составьте таблицы умножения однозначных чисел в троичной и пятеричной системах счисления.

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

а) 10111012 и 11101112;	д) 378 и 758;	и) A16 и F16;
б) 1011,1012 и 101,0112;	е) 1658 и 378;	к) 1916 и C16;
в) 10112, 112 и 111,12;	ж) 7,58 и 14,68;	л) A,B16 и E,F16;
г) 10112, 11,12 и 1112;	з) 68, 178 и 78;	м) E16, 916 и F16.

7.17. В каких системах счисления выполнены следующие сложения? Найдите основания каждой системы:

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

7.19. Вычтите:

а) 1112 из 101002;	д) 158 из 208;	и) 1А16 из 3116;
б) 10,112 из 100,12;	е) 478 из 1028;	к) F9E16 из 2А3016;
в) 111,12 из 100102;	ж) 56,78 из 1018;	л) D,116 из B,9216;
г) 100012 из 1110,112;	з) 16,548 из 30,018;	м) ABC16 из 567816.

7.20. Перемножьте числа, а затем проверьте результаты, выполнив соответствующие десятичные умножения:

а) 1011012 и 1012;	д) 378 и 48;
б) 1111012 и 11,012;	е) 168 и 78;
в) 1011,112 и 101,12;	ж) 7,58 и 1,68;
г) 1012 и 1111,0012;	з) 6,258 и 7,128.

Ответ

7.21. Разделите 100101102 на 10102 и проверьте результат, умножая делитель на частное.

7.22. Разделите 100110101002 на 11002 и затем выполните соответствующее десятичное и восьмеричное деление.

7.23. Вычислите значения выражений:

а) 2568 + 10110,12. (608 + 1210) - 1F16;

б) 1AD16 - 1001011002: 10102 + 2178;

в) 101010 + (10616 - 110111012) 128;

г) 10112. 11002: 148 + (1000002 - 408).

7.24. Расположите следующие числа в порядке возрастания:

а) 748, 1100102, 7010, 3816;

б) 6E16, 1428, 11010012, 10010;

в) 7778, 1011111112, 2FF16, 50010;

г) 10010, 11000002, 6016, 1418.

7.25. Прочитайте стихотворение. Переведите встречающиеся в нем числительные из двоичной системы счисления в десятичную.

Необыкновенная девчонка А. Н. Стариков
Ей было тысяча сто лет, Она в 101-ый класс ходила, В портфеле по сто книг носила – Все это правда, а не бред. Когда, пыля десятком ног, Она шагала по дороге, За ней всегда бежал щенок С одним хвостом, зато стоногий.	Она ловила каждый звук Своими десятью ушами, И десять загорелых рук Портфель и поводок держали. И десять темно-синих глаз Рассматривали мир привычно,… Но станет все совсем обычным, Когда поймете наш рассказ.

7.26. За праздничным столом собрались 4 поколения одной семьи: дед, отец, сын и внук. Их возраст в различных системах счисления записывается так 88 лет, 66 лет, 44 года и 11 лет. Сколько им лет в десятичной системе счисления, если через год их возраст в тех системах счисления можно будет записать как 100?

ОТВЕТЫ К ЗАДАНИЯМ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

7.1. в) троичная: 0, 1, 2, 10, 11, 12, 20, 21, 22, 100, 101, 102, 110, 111, 112, 120, 121, 122, 200, 201; г) пятеричная: 0, 1, 2, 3, 4, 10, 11, 12, 13, 14, 20, 21, 22, 23, 24, 30, 31, 32, 33, 34.

7.2. а) 10₂; б) 110₂; в) 1000₂; г) 10000₂; д) 101100₂; е) 2₈; ж) 10₈; з) 40₈; и) 200₈; к) 10000₈; л) 10₁₆; м) 20₁₆; н) 100₁₆; о) 9AFA₁₆; п) CDF0₁₆.

7.3. а) 1₂; б) 1001₂; в) 111₂; г) 1111₂; д) 10011₂; е) 7₈; ж) 17₈; з) 77₈; и) 107₈; к) 777₈; л) F₁₆; м) 1F₁₆; н) FF₁₆; о) A0F₁₆; п) FFF₁₆.

7.4. Четное двоичное число оканчивается цифрой 0, нечетное двоичное — цифрой 1, четное троичное — цифрами 0, 1 или 2.

7.5. а) 7; б) 511; в) 4091.

7.6. а) ни в какой; б) в шестеричной.

7.7. Основание 5.

7.8. а) 91; б) 183; в) 225; г) ³⁵/₆₄; д) 52,75; е) 335; ж) 520; з) 668; и) ⁷/₁₆; к) 83³³/₆₄; л) 31; м) 2748; н) 4112; о) ⁴¹/₆₄; п) 478²⁵/₃₂.

7.9. а) 1111101₂; 175₈; 7D₁₆; б) 11100101₂; 345₈; E5₁₆; в) 1011000₂; 130₈; 58₁₆; г) 100101,01₂; 45,2₈; 25,4₁₆; д) 11001110,001₂; 316,1₈; CE,2₁₆.

7.10. а) 11767,34₈; 13F7,7₁₆; б) 1653,564₈; 3AB,BA₁₆; в) 271,547₈; B9,B38₁₆; г) 13634,6₈; 179C,C₁₆; д) 27,7674₈; 17,FBC₁₆; е) 1425,62₈; 315,C8₁₆.

7.11. а) 1011001110₂; 1316₈; б) 1001111101000000₂; 117500₈; в) 10101011110011011110₂; 2536336₈; г) 1000000010000,000100000001₂; 10020,0401₈; д) 1101010111100,10011101₂; 15274,472₈.

7.12. а) 101101₂, 101110₂, 101111₂, 110000₂; б) 202₃, 210₃, 211₃, 212₃, 220₃, 221₃, 222₃, 1000₃; в) 14₈, 15₈, 16₈, 17₈, 20₈; г) 28₁₆, 29₁₆, 2A₁₆, 2B₁₆, 2C₁₆, 2D₁₆, 2E₁₆, 2F₁₆, 30₁₆;

7.13. а) 47₁₀ - 101111₂ - 57₈ - 47₁₀ - 57₈ - 101111₂ - 2F₁₆ - 47₁₀ - 2F₁₆ - 101111₂ - 47₁₀; б) 79₁₀ - 1001111₂ - 117₈ - 79₁₀ - 117₈ - 1001111₂ - 4F₁₆ - 79₁₀ - 4F₁₆ - 1001111₂ - 79₁₀.

	+
+

	x
x

7.16. а) 11010100₂; б) 10001,0₂; в) 10101,1₂; г) 11001,1₂; д) 134₈; е) 224₈; ж) 24,3₈; з) 34₈; и) 19₁₆; к) 25₁₆; л) 19,A₁₆; м) 26₁₆.

7.17. а) в 16-й; б) в 10-й; в) в 3-й; г) в 8-й; д) в 16-й.

7.18. в) А=9, B=4, C=5, D=3, F=1, L=0, M=7, N=8; г) A=3, B=6, C=2, D=5, E=9, F=7, G=1, H=0, I=4, J=8; д) A=9, B=3, C=4, D=2, E=1, F=8, G=0, H=7, I=6.

7.19. а) 1101₂; б) 1,11₂; в) 1010,1₂; г) -10,01₂; д) 3₈; е) 33₈; ж) 22,1₈; з) 11,25₈; и) 17₁₆; к) 1A92₁₆; л) -1,7E₁₆; м) 4BBC₁₆.

7.20. а) 11100001₂; б) 11000110,01₂; в) 1000000,101₂; г) 1001011,101₂; д) 174₈; е) 142₈; ж) 15.26₈; з) 55.2222₈.

7.21. 1111₂.

7.22. 1100111₂; 103₁₀; 147₈.

7.23. а) 1493₁₀; б) 542₁₀; в) 1420₁₀; г) 11₁₀.

7.24. а) 110010₂, 38₁₆, 74₈, 70₁₀; б) 142₈, 100₁₀, 1101001₂, 6E₁₆; в) 101111111₂, 500₁₀, 777₈, 2FF₁₆; г) 1100000₂, 60₁₆, 141₈, 100₁₀.

7.25. 1100₂ = 12₁₀; 101₂ = 5₁₀; 100₂ =4₁₀; 10₂ = 2₁₀.

7.26. Дед: 88₉ = 80₁₀; Отец: 66₇ = 48₁₀; Сын:44₅ = 24₁₀; Внук: 11₂ = 3₁₀.

ГЛАВА 8. АЛГЕБРА ЛОГИКИ

8.1. Возникновение логики
как самостоятельной науки

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

Логику, основанную Аристотелем ( 384–322 до н. э. - крупнейший древнегреческий мыслитель ), принято называть формальной. Это название закрепилось за ней потому, что она возникла и развилась как наука о формах мышления.

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

Для того чтобы рассуждать, человеку необходим какой-либо язык. Не удивительно, что математическая логика начиналась с анализа того, как говорят и пишут люди на естественных языках. Этот анализ привёл к тому, что выяснилось существование формулировок, которые невозможно разделить на истинные и ложные, но, тем не менее, выглядят осмысленным образом. Это приводило к возникновению парадоксов, в том числе в одной из фундаментальных наук математики. Тогда было решено создать искусственные формальные языки, лишённого «вольностей» языка естественного.

Рис. 8. 1. Джордж Буль – английский математик-самоучка

Джордж Буль (1815-1864г) по праву считается отцом математической логики (рис. 8.1). Его именем назван раздел математической логики – булева алгебра.

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

Через некоторое время стало понятно, что система Буля хорошо подходит для описания электрических переключателей схем. Ток в цепи может либо протекать, либо отсутствовать, подобно тому как утверждение может быть либо истинным, либо ложным.

А еще несколько десятилетий спустя, уже в ХХ столетии, ученые объединили созданный Джорджем Булем математический аппарат с двоичной системой счисления, заложив тем самым основы для разработки цифрового электронного компьютера.

Рис. 8. 2. Клод Шеннон – американский математик

В 1936 году выпускник Мичиганского университета Клод Шеннон (1916-2001г), которому был тогда 21 год, сумел ликвидировать разрыв между алгебраической теорией логики и ее практическим приложением (рис. 8.2).

Шеннон, имея два диплома бакалавра - по электротехнике и по математике, выполнял обязанности оператора на неуклюжем механическом вычислительном устройстве под названием "дифференциальный анализатор"

Постепенно у Шеннона стали вырисовываться контуры устройства компьютера. Если построить электрические цепи в соответствии с принципами булевой алгебры, то они могли бы выражать логические отношения, определять истинность утверждений, а также выполнять сложные вычисления. Свои идеи относительно связи между двоичным исчислением, булевой алгеброй и электрическими схемами Шеннон развил в докторской диссертации, опубликованной в 1938 году.

Применение в вычислительной технике и информатике алгебры логики

После изготовления первого компьютера стало ясно, что при его производстве возможно использование только цифровых технологий – ограничение сигналов связи единицей и нулём для большей надёжности и простоты архитектуры ПК. Благодаря своей бинарной природе, математическая логика получила широкое распространение в ВТ и информатике. Были созданы электронные эквиваленты логических функций, что позволило применять методы упрощения булевых выражений к упрощению электрической схемы. Кроме того, благодаря возможности нахождения исходной функции по таблице позволило сократить время поиска необходимой логической схемы.

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

Математический аппарат алгебры логики очень удобен для описания того, как функционируют аппаратные средства компьютера, поскольку основной системой счисления в компьютере является двоичная, в которой используются цифры 1 и 0, а значений логических переменных тоже два: “1 - истина” и “0 - ложь”.

Из этого следует два вывода:

1. Одни и те же устройства компьютера могут применяться для обработки и хранения как числовой информации, представленной в двоичной системе счисления, так и логических переменных.
2. На этапе конструирования аппаратных средств алгебра логики позволяет значительно упростить логические функции, описывающие функционирование схем компьютера, и, следовательно, уменьшить число элементарных логических элементов компьютера.

Логический элемент компьютера — это часть электронной логичеcкой схемы, которая реализует элементарную логическую функцию.

Логическими элементами компьютеров являются электронные схемы И, ИЛИ, НЕ, И—НЕ, ИЛИ—НЕ и другие (называемые также вентилями), а также триггер. Триггер имеет два устойчивых состояния, одно из которых соответствует двоичной единице, а другое — двоичному нулю.

Термин триггер происходит от английского слова trigger — защёлка, спусковой крючок. Для обозначения этой схемы в английском языке чаще употребляется термин flip-flop, что в переводе означает “ хлопанье ”. Это звукоподражательное название электронной схемы указывает на её способность почти мгновенно переходить (“ перебрасываться ”) из одного электрического состояния в другое и наоборот. Поскольку один триггер может запомнить только один разряд двоичного кода, то для запоминания байта нужно 8 триггеров, для запоминания килобайта, соответственно, 8 х 2¹⁰ = 8192 триггеров. Современные микросхемы памяти содержат миллиарды триггеров.

8.2. Понятие “алгебры логики” как науки об общих операциях над логическими высказываниями[10]

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

Логическое высказывание — это любoе повествовательное пpедлoжение, в oтнoшении кoтopoгo мoжно oднoзначнo сказать, истиннo oнo или лoжнo.

Так, например, предложение "Меню в программе – это список возможных вариантов" следует считать высказыванием, так как оно истинное. Предложение "Город Джакарта – столица Микронезии" тоже высказывание, так как оно ложное.

Разумеется, не всякое предложение является логическим высказыванием. Высказываниями не являются, например, предложения "Какого цвета этот дом?" и "Эта тема скучна". Первое предложение вопросительное, а не повествовательное. Второе использует слишком неопределённое понятие "тема скучна".

Предложения типа "Рикки Мартин – самый популярный певец" не являются высказываниями, так как для выяснения его истинности или ложности нужны дополнительные сведения: о каком конкретно регионе, или о какой группе людей идет речь. Такие предложения называются высказывательными формами.

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

Алгебра логики рассматривает любое высказывание только с одной точки зрения — является ли оно истинным или ложным. Часто трудно установить истинность высказывания. Так, например, высказывание "Численность жителей города Красноярска составляет 961 тыс. чел" может быть одновременно истинным и ложным. Ложным — так как указанное значение неточное и вообще не является постоянным. Истинным — если рассматривать его как некоторое приближение, приемлемое на практике.

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

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

Чтобы обращаться к логическим высказываниям, им назначают имена. Пусть через А обозначено высказывание "Зимой люди катаются на коньках", а через В — высказывание "Зимой люди катаются на лыжах".

Тогда составное высказывание "Зимой люди катаются на коньках и на лыжах" можно кратко записать как А и В. Здесь "и" — логическая связка, А, В — логические переменные, которые мoгут принимать только два значения — "истина" или "ложь", обозначаемые, соответственно, "1" и "0".

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

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

НЕ. Операция, выражаемая словом " НЕ ", называется отрицанием и обозначается чертой над высказыванием (или знаком ). Высказывание истинно, когда A ложно, и ложно, когда A истинно. Пример. "Луна — спутник Земли" (А); "Луна — не спутник Земли" (). Таблица истинности логической операции " не " приведена в табл. 8.1.

Таблица истинности логического отрицания "НЕ"

Таблица 8. 1

x

И. Операция, выражаемая связкой " И ", называется конъюнкцией (лат. conjunctio — соединение) или логическим умножением и обозначается точкой ". " (может также обозначаться знаками или *). Высказывание А ^. и В истинно тогда и только тогда, когда оба высказывания А и В истинны. Например, высказывание " 10 делится на 2 и 5 больше 3 " истинно, а высказывания " 10 делится на 2 и 5 не больше 3" — ложны. Таблица истинности логической операции " и " приведена в табл. 8.2.

Таблица истинности логического умножения (конъюнкции) " И "

Таблица 8. 2

Х	У	Х^У

ИЛИ. Операция, выражаемая связкой "ИЛИ" (в неисключающем смысле этого слова), называется дизъюнкцией (лат. disjunctio — разделение) или логическим сложением и обозначается знаком v (или плюсом). Высказывание А v В ложно тогда и только тогда, когда оба высказывания А и В ложны. Например, высказывание " 10 не делится на 2 или 5 не больше 3 " ложно, а высказывания "10 делится на 2 или 5 больше 3", — истинны. Таблица истинности логической операции " или " приведена в табл. 8.3.

Таблица истинности логического сложения (дизъюнкции) " ИЛИ "

Таблица 8. 3

Х	У	ХVУ

ЕСЛИ-ТО. Операция, выражаемая связками "если..., то", "из... следует", "... влечет...", называется импликацией (лат. implico — тесно связаны) и обозначается знаком или . Высказывание ложно тогда и только тогда, когда А истинно, а В ложно. Таблица истинности логической операции " импликация " приведена в табл. 8.4.

Таблица истинности импликации "ЕСЛИ-ТО "

Таблица 8. 4

х	у	х—›у

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

РАВНОСИЛЬНО. Операция, выражаемая связками "тогда и только тогда", "необходимо и достаточно", "... равносильно...", называется эквиваленцией или двойной импликацией и обозначается знаком или ~. или ÛВысказывание истинно тогда и только тогда, когда значения А и В совпадают. Например, высказывание "24 делится на 6 тогда и только тогда, когда 24 делится на 3 - истино, а высказывание "24 делится на 6 тогда и только тогда, когда 24 делится на 5" - ложно. Таблица истинности логической операции " эквиваленции " приведена в табл. 8.5.

Таблица истинности эквиваленция, связка "Тогда и только тогда" Таблица 8. 5

х	у	х‹—›у

Импликацию можно выразить через дизъюнкцию и отрицание:

А В = v В.

Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию:

А В = (v В) ^. (v А).

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

Порядок выполнения логических операций задается круглыми скобками. Но для уменьшения числа скобок договорились считать, что сначала выполняется операция отрицания ("не"), затем конъюнкция ("и"), после конъюнкции — дизъюнкция ("или") и в последнюю очередь — импликация.

8.3. логическая формул.
законы алгебрЫ логики

Логические формулы

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

Всякая логическая переменная и символы "истина" ("1") и "ложь" ("0") — формулы.

Если А и В — формулы, то , А ^. В, А v В, А B, А В — формулы.

В качестве примера рассмотрим высказывание " Если я куплю яблоки или абрикосы, то приготовлю фруктовый пирог ". Это высказывание формализуется в виде (A v B) C.

Как показывает анализ формулы (A v B) C, при определённых сочетаниях значений переменных A, B и C она принимает значение "истина", а при некоторых других сочетаниях — значение "ложь" (разберите самостоятельно эти случаи). Такие формулы называются выполнимыми.

Некоторые формулы принимают значение "истина" при любых значениях истинности входящих в них переменных. Таковой будет, например, формула А v , соответствующая высказыванию " Этот треугольник прямоугольный или косоугольный ". Эта формула истинна и тогда, когда треугольник прямоугольный, и тогда, когда треугольник не прямоугольный. Такие формулы называются тождественно истинными формулами или тавтологиями. Высказывания, которые формализуются тавтологиями, называются логически истинными высказываниями.

В качестве другого примера рассмотрим формулу А ^* , которой соответствует, например, высказывание " Катя самая высокая девочка в классе, и в классе есть девочки выше Кати ". Очевидно, что эта формула ложна, так как либо А, либо обязательно ложно. Такие формулы называются тождественно ложными формулами или противоречиями. Высказывания, которые формализуются противоречиями, называются логически ложными высказываниями.

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

Равносильность двух формул алгебры логики обозначается символом "=" или символом "" Замена формулы другой, ей равносильной, называется равносильным преобразованием данной формулы.

Основные законы алгебры логики

В алгебре логики выполняются следующие основные законы, позволяющие производить тождественные преобразования логических выражений (табл. 8.6):

Основные законы алгебры логики

Таблица 8. 6

Закон	Для ИЛИ	Для И
Переместительный
Сочетательный
Распределительный
Правила де Моргана
Идемпотенции
Поглощения
Склеивания
Операция переменной с ее инверсией
Операция с константами
Двойного отрицания

Дата добавления: 2014-01-06