Реферат: Методические указания для подготовительных курсов Ростов-на-Дону

Министерство образования и науки российской федерации

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ


«РОСТОВСКИЙ ГОСУДАРСТВЕННЫЙ СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ»


Системы счисления и основы логики


Методические указания для подготовительных курсов


Ростов-на-Дону

2011

УДК 618.3.06

Системы счисления и основы логики: Методические указания для подготовительных курсов. – Ростов н/Д: Рост. гос. строит. ун-т, 2011.– 20 с.


Изложены основные понятия систем счисления и логики высказываний.


Составители: канд. физ.-мат. наук, доц.

О. А. Ильичева

канд. физ.-мат. Наук, доц.

М. Н. Богачева


Рецензенты: д-р техн. наук, проф. Г.И. Белявский,

д-р техн. наук, проф. А.В. Чернов


© Ростовский государственный строительный университет, 2011

1. Представление числовой информации


1.1. Системы счисления


Система счисления – это способ представления чисел и соответствующие ему правила действия над числами. Разнообразные системы счисления, которые существовали и раньше и которые используются и в наше время, можно разделить на непозиционные и позиционные. Знаки, используемые при записи чисел, называются цифрами.

В непозиционных системах счисления от положения цифры в записи числа не зависит величина, которую она обозначает. Примером непозиционной системы счисления является римская система (римские цифры).

В позиционных системах счисления величина, обозначаемая цифрой в записи числа, зависит от ее позиции. Количество используемых цифр называется основанием позиционной системы счисления.

Система счисления, применяемая в современной математике, является позиционной десятичной системой. Ее основание равно десяти, т.к. запись любых чисел производится с помощью десяти цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

Позиционный характер этой системы счисления легко понять на примере многозначного числа. Например, в числе 333 первая тройка означает три сотни, вторая – три десятка, третья – три единицы.

Для записи чисел в позиционной системе с основанием n нужно иметь алфавит из n цифр. Обычно для этого при n<10 используют n первых арабских цифр, а при n>10 к десяти арабским цифрам добавляют буквы (табл. 1).


Таблица 1

Алфавиты систем счисления

Основание

Название

Алфавит

n=2

Двоичная

0 1

n=3

Троичная

0 1 2

n=8

Восьмеричная

0 1 2 3 4 5 6 7

n=16

Шестнадцатеричная

0 1 2 3 4 5 6 7 8 9 A B C D E F


Если требуется указать основание системы, к которой относится число, то оно приписывается нижним индексом к этому числу. Например:

.

Позиция цифры в числе называется разрядом. Разряд числа возрастает справа налево от младших разрядов к старшим. Число 55510 записано в привычной для нас свернутой форме. Если расписать число, используя различные степени числа 10, то получим следующее выражение 55510= =500+50+5=. Таким образом, число в позиционной системе счисления записывается в виде суммы числового ряда степеней основания (в данном случае 10), в качестве коэффициентов которых выступают цифры данного числа.

Пример С1. Получить развернутую форму десятичных чисел 32478; 26,31.

Решение.



.


. 

В общем случае развернутой формой записи числа называется запись в виде

.

Здесь – само число; – основание системы счисления; – цифры данной системы счисления; – число разрядов целой части числа; – число разрядов дробной части числа.

Например, развернутая запись числа .

Для перевода чисел из двоичной системы в десятичную используется ряд степеней двойки (табл. 2).


Таблица 2

Степени числа 2


Значение степени

1024

512

256

128

64

32

16

8

4

2

1

Показатель степени

10

9

8

7

6

5

4

3

2

1

0


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


Пример С2. Перевести число из двоичной системы в десятичную систему счисления.

Решение. Над числом запишем степени основания двоичной системы, т.е. степени двойки, затем рассмотрим развернутую запись числа, где q=2, n=6, m=0.




1.2. Перевод десятичных чисел в другие системы счисления


Перевод целых чисел производят следующим образом:

1) основание новой системы счисления выразить в десятичной системе счисления и все последующие действия производить в десятичной системе счисления;

2) последовательно выполнять деление данного числа и получаемых неполных частных на основание новой системы счисления до тех пор, пока не получим неполное частное, меньшее делителя;

3) полученные остатки, являющиеся цифрами числа в новой системе счисления, привести в соответствие с алфавитом новой системы счисления;

4) составить число в новой системе счисления, записывая его, начиная с последнего частного.


Пример С3. Перевести число в двоичную систему счисления.

Решение. Для обозначения цифр в записи числа используем символику: .


_37

2
















36

_18

2










Отсюда .



18

_9

2















8

_4

2















4

_2

2















2

1=

























Пример С4. Как представляется число в двоичной системе счисления?

1) , 2) , 3) , 4) , 5) .

Решение. Число целое, поэтому для решения поставленной задачи можно воспользоваться алгоритмом, приведенным выше.

_25

2













24

_12

2







Отсюда .



12

_6

2












6

_3

2












2
























Другой способ решения – перевести каждое из двоичных чисел в десятичную систему счисления.

1)

2)

3)

4)

5)

Ответ: 2. 

Перевод дробных чисел


1. Основание новой системы счисления выразить в десятичной системе счисления и все последующие действия производить в десятичной системе счисления.

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

3. Полученные целые части произведений, являющиеся цифрами числа в новой системе счисления, привести в соответствие с алфавитом новой системы счисления.

4. Составить дробную часть числа в новой системе счисления, начиная с целой части первого произведения.



0,

1875




 2

0,

3750




 2

0,

7500




 2

1,

5000




 2

1,

0000
^ Пример С5. Перевести десятичную дробь 0,1875 в двоичную систему счисления.


Отсюда (Необходимо выписать все целые части произведений сверху вниз). 


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


Пример С6. Перевести в двоичную систему счисления с точностью до 4 знака.

Решение. Целую часть будем делить на 2, а дробную умножать на 2 (до пяти значащих цифр).


_23

2


















0,56

22

_11

2













2

1

10

_5

2












1,12




1

4

_2

2







2







1

2

1









0,24










0










2
























0,48






















2
























1,96






















2






















1,92


Отсюда , а дробная часть . Таким образом, .


1.3. Арифметические операции в двоичной и кратных

ей системах счисления


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


0+0=0






0+1=1






1+0=1






1+1=10







Важно обратить внимание на то, что при сложении двух единиц происходит переполнение разряда и производится перенос в старший разряд. Переполнение разряда наступает тогда, когда величина числа в нем становится равной или большей основания. Проверим, действительно ли 12+12=102: переведем слагаемые в десятеричную систему счисления. 12=110, поэтому 12+12=110+110=210=102.

10>
Пример С7. Найти сумму чисел и .

Решение

Первое слагаемое

1010101




+

Второе слагаемое

0110111

Сумма

10001100


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









Как видим, действительно 85+55=140. 


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


Приведем в качестве примера запись натуральных чисел от единицы до шестнадцати в четырех системах счисления. Для удобства перевода из двоичной в восьмеричную и шестнадцатеричную системы рассмотрим табл.3.


Таблица 3

Перевод чисел из одной системы счисления в другую


10-я

2-я

8-я

16-я

2-8

2-16

0

0

0

0

000

0000

1

1

1

1

001

0001

2

10

2

2

010

0010

3

11

3

3

011

0011

4

100

4

4

100

0100

5

101

5

5

101

0101

6

110

6

6

110

0110

7

111

7

7

111

0111

8

1000

10

8




1000

9

1001

11

9




1001

10

1010

12

A




1010

11

1011

13

B




1011

12

1100

14

C




1100

13

1101

15

D




1101

14

1110

16

E




1110

15

1111

17

F




1111

16

10000

20

10








Из этой таблицы видно, что в двоичной системе счисления запись второй восьмерки чисел (от 8 до 15) отличается от записи первой восьмерки (от 0 до 7) наличием единицы в четвертом (слева) разряде. На этом основан алгоритм перевода двоичных чисел в восьмеричные «по триадам». Для применения этого алгоритма надо разбить двоичное число на тройки цифр (естественно, отсчитывая справа по три цифры для целого числа и слева для дробного числа) и записать вместо каждой из троек восьмеричную цифру.


^ Пример С8. Перевести число в восьмеричную систему счисления.

Решение

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

.

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

Например, .

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


^ Пример С9. Перевести двоичное число 110111101011101111,101 в шестнадцатеричную систему счисления.

Решение. Разделим данное число на группы по четыре цифры, начиная справа для целой части числа и слева для дробной части числа. Если в крайней левой группе (для целой части) и в крайней правой(для дробной части) окажется меньше четырех цифр, то дополним их нулями.



Следовательно, .


^ Пример C10. Вычислите сумму чисел x и y, если . Результат представьте в виде восьмеричного числа.


Варианты ответа:

Есть два способа решения. Первый способ – сложить числа по правилам сложения двоичных чисел (столбиком), а результат перевести в восьмеричную систему счисления. Второй способ состоит в том, чтобы сначала числа перевести в восьмеричную систему, а потом сложить их.

Ответ: 3). 


Пример С11. Вычислить значение суммы в десятичной системе счисления:

Варианты ответа:

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

Ответ: 2). 


^ Пример С12. B шестнадцатеричной системе счисления сумма чисел F16 и 10112 равна

Варианты ответа: 1) 1A16; 2) 3216; 3) 1B16; 4) 2A16; 5) 1C16.

При решении задачи можно число F16 перевести в двоичную систему, затем числа сложить столбиком, а результат перевести в шестнадцатеричную систему.

Ответ: 1). 


^ Пример С13. B шестнадцатеричной системе счисления произведение чисел A416 и 68 равно

Варианты ответа: 1) 8416; 2) 98416; 3) 8D316; 4) 331816; 5) 3D816.

При решении задачи числа A416 и 68 переводим в двоичную систему, умножаем их по правилу умножения двоичных чисел, результат переводим в шестнадцатеричную систему счисления.

Ответ: 5). 


^ Пример С14. Какое минимальное основание имеет система счисления, если в ней записаны числа 100, 543, 101?

Варианты ответа: 1) нет верного ответа; 2) 2; 3) 5; 4) 4; 5) 6.

Необходимо ориентироваться на алфавит записи числа, помня что, например, в восьмеричной системе алфавит состоит из 8 цифр (0, 1, 2, 3, 4, 5, 6, 7).

Ответ: 5). 


1.4 Упражнения по теме для самостоятельного решения


Переведите целые числа из десятичной системы счисления в двоичную:

а) 513; в) 600; д) 602; ж) 1000;

б) 2304; г) 5001; е) 7000; з)8192.

Переведите десятичные дроби в двоичную систему счисления (ответ записать с шестью двоичными знаками):

а) 0,4622; в) 0,5198; д) 0,5803; ж) 0,6124;

б) 0,7351; г) 0,7982; е) 0,8544; з) 0,9321.

Переведите смешанные десятичные числа в двоичную систему счисления: а) 40,5; б) 31,75; в) 124,25; г) 125,125.

Переведите целые числа из десятичной в восьмеричную систему счисления: а) 8700; б) 8888; в) 8900; г) 9300.

Переведите целые числа из десятичной в шестнадцатеричную систему счисления: а) 266; б) 1023; в) 1280; г) 2041.

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

а) 0,43; б) 37,41; в) 2936; г) 481,625.

Переведите числа из десятичной системы счисления в шестнадцатеричную: а) 0,17; б) 43,78; в) 25,25; г) 18,5.

Заполните таблицу, в каждой строке которой одно и то же число должно быть записано в системах счисления с основанием 2, 8, 10 и 16.

Основание 2

Основание 8

Основание 10

Основание 16

101010













127













321













2B




Заполните таблицу, в каждой строке которой одно и то же число должно быть записано в системах счисления с основанием 2, 8, 10 и 16.




Основание 2

Основание 8

Основание 10

Основание 16










101







26







361







10110










Переведите двоичные числа в восьмеричную систему счисления:

а) 1010001001011; в) 1011001101111; д) 110001000100;

б) 1010,00100101; г) 1110,01010001; е) 1000,1111001.

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

а) 1010001001011; в) 1011001101111; д) 110001000100;

б) 1010,00100101; г) 1110,01010001; е) 100,1111001.

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

а) 266; в) 1270; 10,23;

б) 266; г) 2а19; е) 10,23.

Составьте таблицу сложения в восьмеричной системе счисления и выполните вычисления:

а) 3456 + 245; б) 7631-456;

в) 77771 +234; г) 77777-237.

Составьте таблицу сложения в шестнадцатеричной системе счисления и выполните вычисления:

а) FFFF+1; б) 1996+BABA;

в) BEDA-BAC; г) 1998-A1F.

15*. Найти основание q системы счисления и цифру n, если верно равенство:

33m5n+2n443=55424

Пример выполнен в системе счисления с основанием q, m – максимальная цифра в этой системе счисления.


Ответы на некоторые упражнения:

1.a) 1000000001; 1.в) 1001011000;

2.а) 0,011101 2.в) 0,100001;

3.a) 101000,1;

4.а) 20774;

5.а) 10A;

6.а) 0,334; 6.б) 45,321;

7.б) 2B,C7A;

10.а) 12113; 10.г) 16,242.


2. Основы логики высказываний


2.1. Высказывания. Логические операции, выражения


Высказывание – это утверждение (предложение), о котором можно сказать, истинно оно или ложно. Например, высказывание «город Сочи расположен на берегу Черного моря» истинно, а высказывание «город Ростов расположен на берегу Черного моря» ложно. Из простых высказываний А, В можно образовать более сложные высказывания: «А и В», «А или В», «неверно, что А», «если А, то В» («из А следует В»). Зная истинность или ложность утверждений А, В, можно установить истинность или ложность сложного (составного) высказывания.

Высказывание можно формализовать с помощью логической формулы. Логическая формула включает в себя логические переменные и логические связки (знаки логических операций). Переменные представляют утверждения и обозначаются обычно буквами латинского или русского алфавита. Связки – это операции:

конъюнкция (обозначения , &, , AND, И);

дизъюнкция (обозначения , +, OR, ИЛИ);

отрицание (обозначения  , , NOT, НЕ, для высказывания А);

импликация (обозначения  , );

эквивалентность (обозначения ,).

Далее используются первые из указанных в списках обозначений.


Например, высказывание «если будет дождь, мы не поедем в гости, будем сидеть дома» можно формально представить формулой А  ВС, где переменная А в данном случае представляет высказывание «будет дождь», В – высказывание «поедем в гости», С – «будем сидеть дома». Прочитать такую формулу можно так: «из А следует не В и С».


Операнды дизъюнкции называют дизъюнктами, операнды конъюнкции – конъюнктами. В импликации    левый операнд, формулу , называют посылкой, а если правый операнд, формулу  – заключением. Читают импликацию как «из  следует », или « влечет ».

^ Приоритеты операций: существует договоренность о порядке выполнения логических операций, если этот порядок не размечен круглыми скобками. Наивысший приоритет имеет отрицание, затем конъюнкция, далее выполняется дизъюнкция и последней – импликация. Если логическое выражение имеет скобки, то они меняют приоритет операций, т.е. сначала выполняются действия в скобках.

^ Чтение формул. Формулы необходимо читать с учетом приоритетов операций. Например, формулу  (х   у)  z можно прочитать так: из того, что не выполняется условие «из х следует не у», вытекает (логически следует) z. Другой правильный вариант: если неверно, что из х следует не у, то выполняется z. Прочтение «если не х, то не у влечет z» является неверным и неоднозначным, т.к. соответствует формуле  х (  у  z ) и формуле ( х   у)  z. 


2.2. Построение формул по высказываниям


Пример Л1. «Для того, чтобы треугольники были равны, необходимо, чтобы они были подобны». Обозначим простые высказывания переменными: x – «треугольники равны» и y – «треугольники подобны». Тогда формула: x  y соответствует исходному высказыванию. Обратите внимание, что необходимое условие идет справа от операции следования: если треугольники равны, то они точно будут подобны. Обратное, y  x, неверно – из подобия равенства не следует. 


Пример Л2. Высказывание: «Для того чтобы были лужи, достаточно, чтобы прошел дождь». Обозначим x – «были лужи», y – «прошел дождь». Формула y  x формализует исходное высказывание. Обратите внимание, что достаточное условие идет слева от операции следования: если был дождь, то есть и лужи. Обратное x  y неверно, т.к. лужи могут быть вызваны не дождем, а например, водопроводной аварией. 


Пример Л3. Высказывание: «Для того чтобы число было четным, необходимо и достаточно, чтобы оно делилось на два без остатка». Обозначим x – «число четное», y – «число делится на два без остатка». Формула (x  y)  (y  x) формализует исходное высказывание. 


Примеры ошибочного толкования следования

1. Из высказываний «все зебры полосаты» и «это животное полосато» следует, что «это животное – зебра». Так, полосатый кот становится зеброй.

2. Из высказываний «людей много» и «Сократ – человек» следует, что «Сократов много».


2.3. Определение истинности формул


Задача определения истинности формул решается в соответствии с принятыми правилами интерпретации высказываний в логике. Обычно цифрой 0 обозначено значение «ложь», цифрой 1 – значение «истина».

На множестве {0, 1} операции , ,   определены при помощи ниже представленных таблиц.

A

A

0

1

1

0


Другими словами, Отрицание истинно тогда и только тогда, когда исходное высказывание A ложно, и ложно, когда исходное высказывание A истинно.

A

B

A  B

0

0

0

0

1

0

1

0

0

1

1

1


Конъюнкция истинна тогда и только тогда, когда оба операнда А и B истинны.

A

B

A  B

0

0

0

0

1

1

1

0

1

1

1

1


Дизъюнкция ложна тогда и только тогда, когда оба операнда А и B ложны.

A

B

A  B

0

0

1

0

1

1

1

0

0

1

1

1


Импликация ложна тогда и только тогда, когда первое высказывание А (посылка, причина) истинно, а второе высказывание В (заключение, следствие) ложно.

A

B

A  B

0

0

1

0

1

0

1

0

0

1

1

1


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

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

Тавтология – это формула, истинная при любой интерпретации входящих в нее переменных. Так, формула x  x всегда истинна. Действительно значение дизъюнкции есть истина, если хотя бы один ее операнд истин, а в этой формуле, если x – ложь, то x – истина.

Противоречие – это формула, ложная при любой интерпретации входящих в нее переменных. Так, формула xx всегда ложна. Действительно, значение конъюнкции есть ложь, если хотя бы один ее операнд ложен, а в этой формуле, если x – истина, то x – ложь.

Если заданы значения переменных, то, используя стандартную интерпретацию, можно определить, истинна или нет данная формула.


.Определение истинности формул с помощью таблиц истинности


Пример Л4. Определить, истинна или нет формула (x   y)  xy, если а) x=1, y=0; б) x=0, y=1.

Решение. Для решения задачи нужно подставить данные значения x и y в формулу и использовать интерпретацию операций, учитывая их приоритет. Так, для а) (1  0)  10   1  0  0  0  1. Ответ: при x=1, y=0 данная формула истинна. Для б) (0  1)  01  (0  0) 0  0  0  1  0  0. Ответ: при x=0, y=1 данная формула ложна. Этот процесс можно представить таблицей:


x

y

 y

x   y

(x   y)

xy

(x   y)  xy

1

0

1

1

0

0

1

0

1

0

0

1

0

0

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


^ Пример Л5. Определить истинность формулы   (xy)  xyz  xyz для всех значений переменных x, y, z.


Решение. Решаем задачу с помощью таблицы, разбивая исходную формулу на подформулы:


x

y

z

xy

(xy)  1

x

y

z

xyz

 2

xyz

 3

12

 4

4  3

 

0

0

0

0

1

1

1

1

1

0

1

0

0

0

1

0

1

1

1

0

1

1

1

1

0

1

0

0

1

1

0

1

1

1

1

1

0

1

1

0

1

1

0

0

1

1

1

1

1

0

0

0

1

0

1

1

1

1

1

1

1

0

1

0

1

0

1

0

1

1

1

1

1

1

0

1

0

0

0

1

1

1

1

1

1

1

1

1

0

0

0

0

0

1

1

1


Создав такую таблицу, можно ответить на вопрос, является ли данная формула тавтологией? Ответ – нет, т.к. при x=0, y=0, z=0 ее значение есть 0, а тавтология истинна при любых x, y, z. Является ли эта формула противоречием? Нет, т.к. есть наборы переменных, при которых она истинна. Из таблицы видно, что, например, «усеченная» формула (xy)  xyz является тавтологией (все ее значения истинны), а соответственно ее отрицание ((xy)  xyz ) будет противоречием (все значения ложны). 


2.5. Упрощение формул


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


1) А  В  В  А

2) (А  В)  С  А  (В  С)

3) А  А  А

4) АВ  ВА

5) (АВ)С  А(ВС)

6) А  А  А

7) А(В  С)  АВ  АС

8) А  (ВС)  (А  В)  (А  С)

9)   А  А

10)  (А  В)  А  В

11)  (АВ)  А  В

12) А  В   А  В

13) А  В   В  А

14) (А  В)  (В  А)

15) А  (АВ)  А

16) А(А  В)  А

17) (АВ)  В  А  В

18) А (В  С)  АВ  С

19) А  В   В  В   В

20) А  В  В  А

21) А(В В)  А

22) А  (В   В)  В   В


Здесь А, В, С – (под)формулы, в частности, логические переменные. Обычно при преобразованиях вначале избавляются от импликаций с помощью правила 12, затем от отрицаний над составными формулами (правила 9–11) и скобок. Если в конечном результате преобразований получена тавтология, например хх, то исходная формула также является тавтологией, т.к. она эквивалентна полученной. Аналогично результат xx говорит о противоречивости исходной формулы. Правило 19 говорит о том, что в дизъюнкции подформула-тавтология и будет результатом, т.к. она всегда истинна, а для истинности дизъюнкции достаточно истинности хотя бы одного операнда. Правило 20 говорит о том, что противоречие не влияет на результат дизъюнкции, т.к. оно всегда ложно и результат определяется истинностью или ложностью оставшейся формулы. Соответственно тавтология не влияет на результат конъюнкции (правило 21), т.к. она всегда истинна и окончательный результат зависит только от значения оставшейся формулы.


^ Пример Л6. Упростить формулу: (xy)(x  y)x.

Решение. Проводим цепочку преобразований (в скобках указывается номер применяемого правила):

(xy)(x  y)x  (12)  (xy)( x  y)x  (11)   x   y  ( x  y)x  (9, 4, 7)  x  y   xx  yx  (20)  x  y  yx  (15)  x  y. 


Пример Л7. Определить, является ли формула (xy)(x  y)x противоречием?

Решение. Проделав упрощения, приведенные в примере 1, получим, что исходная формула эквивалентна формуле x  y, которая противоречием не является. Ответ – нет.


Пример Л8. Определить, является формула x ((y  z) x) тавтологией?

Решение. Упростим формулу: x  ((y  z) x)  (11)  x  (y  z)   x  (1)  x  x  (y  z)  (19)  x   x. Ответ – да. 


2.6. Решение логических задач


Решение логических задач сводится к построению логической формулы и последующему ее упрощению. При этом можно получить ответы на вопросы: является ли рассуждение логически правильным, является ли рассуждение В логическим следствием рассуждения А, совместны ли рассуждения А, В, С, …? Для понимания решения таких задач рассмотрим подробнее эти понятия.

Говорят, что ^ В является логическим следствием А, или А логически влечет В, если формула А  В является тавтологией. Из таблицы истинности для операции  и определения тавтологии следует, что это условие равносильно следующему: если истинно А, то истинно и В.

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

Говорят, что множество утверждений совместно, если конъюнкция формул, соответствующих этим утверждениям, не является противоречием.


^ Пример Л9. Правильно ли рассуждение:

Если Джонс – коммунист, то Джонс – атеист. Джонс – атеист. Следовательно, Джонс – коммунист.

Решение. Обозначим утверждения: А – «Джонс – коммунист», В – «Джонс – атеист». Тогда исходное рассуждение можно представить формулой: (АВ)ВА. Упростим формулу и определим, является ли она тавтологией. Упрощение: избавимся от импликаций, скобок и отрицания по правилам 12, 7, 11, 15: (АВ)В  А   ((АВ) В))  А  В  А. Полученная формула тавтологией не является, следовательно, исходное рассуждение логически неверно. 


^ Пример Л10. Совместны ли утверждения: 1) Если инфляция растет, то увеличивается зарплата и увеличиваются налоги. 2) Налоги растут. 3) Зарплата снижается. 4) Если растет зарплата, то инфляция также растет.

Решение. Обозначим простые высказывания: инфляция растет – А, зарплата увеличивается – В, налоги увеличиваются – С. Запишем утверждения в виде формул: 1) А  ВС; 2) С; 3)  В; 4) В  А. Построим их конъюнкцию, упростим и проверим, будет ли окончательная формула противоречием:

^ (А  ВС)СВ(В  А)  ( А  ВС)  СВ (В  А) 

 ( А  ВС)(СВ  СВА)   АСВ  ВСВ  СВАА  ВСВА   АСВ. Полученная формула непротиворечива, следовательно, исходные утверждения совместны. 


2.7. Упражнения по теме для самостоятельного решения


Записать с помощью формул:

Данное отношение есть отношение эквивалентности тогда и только тогда, когда оно рефлексивно, симметрично и транзитивно.

Для того чтобы число делилось на три, достаточно, чтобы оно делилось на девять.

Если влажность так высока, то либо после полудня, либо вечером будет дождь.

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

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


Проверить истинность формул:

Известно, что эквивалентность x  y истинна. Что можно сказать о значении x  y и x  y ?

Заполнить истинностную таблицу для формулы (PQ)( (PQ)).

Известно, что x имеет значение 1. Что можно сказать о значениях импликации xy  z?

Проверить истинность формулы ((xy)(yz)) (xz) при x=0, y=1, z=0 и при x=1, y=1, z=0.

Построить таблицу истинности для функции Ф(x, y, z)   ( x y)  (x y)x. Является ли она тавтологией?


Преобразование (упрощение) формул:

Противоречива ли формула P  P  РР ?

Является ли тавтологией формула (PQ)  P  QQ ?

Пусть Ф – тождественно ложная формула. Доказать, что xyФ 

x y.

Упростить формулу (xy)(x  y)x.

Найти x, если (x  a)  (x  a)  b.

Проверить эквивалентность формул, преобразовав формулы слева и справа от знака  к одной и той же формуле: (PQ)(PR)  (PQR).

Противоречива, тавтология или ни то, ни другое формула (PQ) (Q  P)  QQ ?

Не строя таблицы истинности, доказать эквивалентность (хy)  xy.

Упростить формулу (x(xx  yy) z)  x  yz  (yz).

Не строя таблицы истинности, доказать эквивалентность x(yz)  xy  z .

Построить таблицу истинности: F = А  ( В  А  В).

Построить таблицу истинности: F = (В   А) ( ВА  АВ).

Построить таблицу истинности: F = (А  В)  (В  А)  (В  А).

На каких наборах переменных А и В истинна функция F = (А  В)  (В  А)  В  А (Ответ: <1, 0> , <1, 1>).

Упростить логическую формулу ( А  В)  (В  С)  С  А (Ответ: А ).

Упростить логическую формулу АВС  С  В (Ответ: А В  С).

Упростить логическую формулу (АВ  С)СВ  D (Ответ: D).

Истинность высказываний: «из двух фирм В и С проводит рекламную акцию только одна» и «фирма А проводит рекламную компанию, а фирма С не проводит – означает проведение рекламных акций какими фирмами? (Ответ: Фирмы A и B проводят рекламную акцию (Логическая формула для первого высказывания : , второго – . Тогда из истинности обоих высказываний следует, что ()  (). Упростим формулу и получим )).



Задания для самостоятельного решения


1. Переведите целые числа из десятичной системы счисления в двоичную:

а) 3204; б) 5100.

2. Переведите десятичные дроби в двоичную систему счисления (ответ записать с шестью двоичными знаками):

а) 0,755; б) 0,787.

3. Переведите смешанное десятичное число в двоичную систему счисления 323,95.

4. Переведите целые числа из десятичной в восьмеричную систему счисления: а) 9080; б) 3090.

Переведите целые числа из десятичной в шестнадцатеричную систему счисления: а) 2180; б) 4201.

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

а) 9326; б) 814, 562.

Переведите двоичные числа в восьмеричную систему счисления: а) 1011010011111; б) 111000000100.

Вычислите сумму чисел x и y, если . Результат представьте в виде восьмеричного числа и в виде шестнадцатеричного числа.

Вычислить значение суммы в десятичной системе счисления: .

B шестнадцатеричной системе счисления сумма чисел 12F16 и 10102 равна?

Проверить истинность формулы ((xy)(yz)) (xz) при x=0, y=0, z=1 и при x=1, y=0, z=1.

Является ли тавтологией формула (PQ)  P  QQ ?

Упростить формулу (x(xx  yy) z)  x  yz  (yz).

Упростить логическую формулу (А ВС)СА  С.

Упростить ло