Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

Логические выражения и операции



Формы мышления

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

Воснове современной логики лежат учения, созданные еще древ­негреческими мыслителями, хотя первые учения о формах и способах мышления возникли в Древнем Китае и Индии. Основоположником формальной логики является Аристотель, который впервые отделил ло­гические формы мышления от его содержания.

Сам термин «логика» происходит от древнегреческого logos, озна­чающего «слово, мысль, понятие, рассуждение, закон».

Логика— это наука о формах и способах мышления. Это учение о спо­собах рассуждений и доказательств.

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

Мышление всегда осуществляется через понятия, высказывания и умозаключения.

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

ПримерПрямоугольник, проливной дождь, компьютер.

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

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

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

 

Пример:Истинное высказывание: «Буква «а» — гласная».

Ложное высказывание: «Компьютер был изобретен в середине XIX века».

 

Заметим, что любое высказывание не может быть одновре­менно истинным и ложным, а принимает только одно из этих двух возможных логических значений: ИСТИНА или ЛОЖЬ. Эти значе­ния называются логическими постоянными, или логическими кон­стантами.

Утверждение — суждение, которое требуется доказать или опровергнуть, например, сумма внутренних углов треугольника равна 180°.

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

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

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

 

Пример:

Дано высказывание: «Все углы равнобедренного треугольника равны».

Получить высказывание «Этот треугольник равносторонний» путем умо­заключений.

 

Пусть основанием треугольника является сторона с. Тогда а=Ь. Так как в треугольнике все углы равны, следовательно, основанием может быть лю­бая другая сторона, например а. Тогда Ь=с. Следовательно а=Ь=с. Треуголь­ник равносторонний.

Выполните упражнение

 

Какие из предложений являются высказываниями? Определите их истинность.

 

1. Какой длины эта лента?

 

2. Прослушайте сообщение.

 

3. Делайте утреннюю зарядку!

 

4. Назовите устройство ввода информации.

 

5. Кто отсутствует?

 

6. Париж — столица Англии.

 

7. Число 11 является простым.

 

8. 4 + 5=10.

 

9. Без труда не вытащишь и рыбку из пруда.

 

10. Сложите числа 2 и 5.

 

11. Некоторые медведи живут на севере.

 

12. Все медведи - бурые.

 

13. Чему равно расстояние от Москвы до Сенкт-Петербурга.

Логические выражения и операции

Подобно тому, как для описания действий над переменными ве­личинами был разработан раздел математики — алгебра, так и для обработки логических выражений в математической логике была создана алгебра высказываний, или алгебра логики. Поскольку осно­вы такой алгебры были заложены в трудах английского математика Джорджа Буля (XIX век), то алгебра логики получила также назва­ние булевой алгебры. Вспомним, что ранее мы уже говорили о том, что решение любой задачи на компьютере сводится к выполнению процессором ряда арифметических и логических операций. Послед­ние как раз и выполняются над логическими выражениями на основе законов и правил булевой алгебры. Таким образом, математический аппарат булевой алгебры позволил формализовать действия над ло­гическими выражениям и явился базой для разработки логических элементов и, в целом, логических основ построения компьютеров.

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

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

Можно определить понятия логической переменной, логической функ­ции и логической операции.

Логическая переменная— это простое высказывание, содержащее только одну мысль. Ее символическое обозначение - латинская буква (например, A,B,X,Y и т.д.). Значением логической переменной могут быть только кон­станты ИСТИНАи ЛОЖЬ (1и 0).

Составное высказывание - логическая функция,которая содержит не­сколько простых мыслей, соединенных между собой с помощью логичес­ких операций. Ее символическое обозначение —F(A,B,...).

На основании простых высказываний могут быть построены составные высказывания.

Логические операции— логическое действие.

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

Логическая операция КОНЪЮНКЦИЯ определяет соединение двух логических выражений (высказываний) с помощью союза И. Эта операция называется также логическим умножением и обозна­чается символами & или ^. Рассмотрим таблицу истинности, определяющую результат этой логической операции над двумя аргумен­тами — простыми логическими выражениями А и В, каждое из ко­торых может принимать логические значения 0 или 1.

 

А В А&В

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

Логическая операция ДИЗЪЮНКЦИЯ определяет логическое со­единение двух логических выражений (высказываний) с помощью союза ИЛИ. Эта операция называется также еще логическим сложе­нием и обозначается значком v. Рассмотрим таблицу истинности, определяющую результат этой логической операции над двумя аргу­ментами — простыми логическими выражениями А и В, каждое из которых может принимать логические значения 0 или 1.

 

А В AvB

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

Логическая операция ОТРИЦАНИЕ, илиИНВЕРСИЯ, определя­ется над одним аргументом (простым или сложным логическим вы­ражением) следующим образом: если исходное выражение истинно, то результат его отрицания будет ложным, и наоборот, если исходное выражение ложно, то его отрицание будет истинным. Данная опера­ция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО. Операция ОТРИЦАНИЕ обо­значается символом , а ее результат определяется следующей таб­лицей истинности:

 

А а

 

 

Логическая операция ИМПЛИКАЦИЯ {логическое следование).

Эта операция связывает два простых логических выражения, из которых первое является условием, а второе — следствием из этого условия. В разговорном языке эта операция выражается словами если... , то... Для ее обозначения в алгебре логики используется зна­чок следования =>. Результат операции импликации для условия А (первое логическое выражение) и условия В (второе логическое вы­ражение) определяется в соответствии со следующей таблицей истин­ности:

 

 

А В А=>В

 

По определению результатом импликации является ЛОЖЬ тогда и только тогда, когда условие (А) истинно, а следствие (В) ложно.

 

Логическая операция ЭКВИВАЛЕНТНОСТЬ (равнозначность) определяет результат сравнения двух простых логических выраже­ний А и В, обозначается символом <=>. Результат этой операции — новое логическое выражение, которое является истинным тогда и только тогда, когда оба исходных выражения одновременно истинны или ложны. Это определение описывается следующей таблицей истинности:

 

 

А В А<=>В

 

Сложным логическим выражениемназывается логическое выра­жение, составленное из одного или нескольких простых (или слож­ных) логических выражений, связанных с помощью рассмотренных логических операций. Если составное высказывание (логическую функцию) выразить в виде формулы, в которую войдут логические переменные и знаки логических операций, то получится логическое выражение,значение которого можно вычислить. Значением логического выражения могут быть только ЛОЖЬ или ИСТИНА. При составлении логического выражения необходимо учи­тывать порядок выполнения логических операций.

Порядок выполнения логических операций в сложном логическом выражении:

1. инверсия — ;

2. конъюнкция — & (или ^);

3. дизъюнкция — v;

4. импликация — =>;

5. эквивалентность — <=>.

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

 

Например, А, В и С — три простых логических выражения. Одним из примеров составленного из них сложного логического вы­ражений будет:

D = (AvB&C)

Пример

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

 

1. Проанализируем составное высказывание.

Оно состоит из следующих простых высказываний: «Петя поедет в дерев­ню», «Будет хорошая погода», «Он пойдет на рыбалку». Обозначим их через логические переменные:

A = Петя поедет в деревню;

В = Будет хорошая погода;

С = Он пойдет на рыбалку.

2. Запишем высказывание в виде логического выражения, учитывая по рядок действий. Если необходимо, расставим скобки:

F = A&(B=>С).

 

Выполните упражнение

 

I. Есть два простых высказывания: А - «Число 10 - четное»; В - «Волк - травоядное животное».

Составьте из них все возможные составные высказывания и определите их истинность.

 

II. Запишите следующие высказывания в виде логических выражений.

1. Число 17 нечетное и двузначное.

2. Неверно, что корова - хищное животное.

3. На уроке физики ученики выполняли лабораторную работу и сообщали результаты ис следований учителю.

4. Если число делится на 2, то оно - четное.

5.Переходи улицу только на зе­леный свет.

6. На уроке информатики необходимо соблюдать особые правила поведе­ния.

7. При замерзании воды выделяется тепло.

8. Если Маша - сестра Саши, то Саша - брат Маши.

9. Если компьютер включен, то можно на нем работать.

10. Водительские права можно получить тогда и только тогда, когда тебе ис­полнится 18 лет.

11. Компьютер выполняет вычисления, если он включен.

12. Ты можешь купить в магазине продукты, если у тебя есть деньги.

13. Тише едешь - дальше будешь.

 

III. Даны высказывания: А — «р делится на 5» и В — «р — нечетное число». Найти множество значений р, при которых результат

а) логического сложе­ния и

б) логического умножения будет:

1)истинным;

2)ложным.

 

IV. Составьте и запишите истинные сложные высказывания из простых с ис­пользованием логических операций.

1. Неверно, что 10>Y≥5 и Z<0

2. Z является min(Z,Y).

3. А является max(A,B,C).

4. Любое из чисел X,Y,Z положительно.

5. Любое из чисел X,Y,Z отрицательно.

6. Хотя бы одно из чисел K,L,M не отрицательно.

7. Хотя бы одно из чисел X,Y,Z не меньше 12.

8. Все числа X,Y,Z равны 12.

9. Если X делится на 9, то X делиться и на 3.

10. Если X делится на 2, то оно четное.

 

V. Найдите значения логических выражений:

1. F = (0 v 0) v (l v l)

2. F = (l v l) v (l v 0)

3. F = (0 & 0) & (1 & 1)

4. F = 1 & (1 v 1) v (0 & 1)

5. F = (1 v 1) & (1 v1) & (1 v 0)

 

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

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

Для составления таблицы необходимо:

1. Выяснить количество строк в таблице (вычисляется как 2П, где п - ко­личество переменных).

2. Выяснить количество столбцов = количество переменных + количес­тво логических операций.

3. Установить последовательность выполнения логических операций.

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

5. Заполнить таблицу истинности по столбцам.

 

 

Пример 1

Построим таблицу истинности для выражения F = (A v B) & (A vB)..

· Количество строк = 22 (2 переменных) + 1 (заголовки столбцов) = 5.

· Количество столбцов = 2 логические переменные (А, В) + 5 логических операций (v, &, , v, ) = 7.

· Расставим порядок выполнения операций: 15 2 4 3 (A v B)&( A v B)

Построим таблицу:

 

А В A v B А В AvB (AvB)&(AvB)

 

 

Пример 23 2 1

Построим таблицу истинности для логического выражения F=X v Y& Z.

1. Количество строк = 23+1 = 9.

2. Количество столбцов = 3 логические переменные + 3 логических опера­ций = 6.

3. Укажем порядок действий: 3 2 1

4. Нарисуем и заполним таблицу.

 

     
X Y Z Z Y&Z XvY&Z

 

Выполните упражнение

Составьте таблицы истинности для следующих логических выражений:

 

1. F = (X & Y) v Z.

2. F= A ↔ B v A&C

3. F=A& (B↔C)

4. F = (X v Y) & (Y ↔ X).

5. F= A ↔ B v C

6. F=(AvB) → (AvC)

7. F= А ↔ (В v C)

8. F = A & B → C & D.

9. F= A ↔ B &C

10. F = (X v Y) & (Y v X).

11. F= A ↔ B &C

12. F = (A v B) & (B v A→ B).

13. F= A ↔ B v A &C

14. F= A → B v A&C

15. F = X & Y v X.

16. F = ((X v Y) & (Z → X)) & (Z v Y).

17. F= A → B v A &C

18. F= А →(В v C)

19. F= A ↔ B v C

20. F = ((X v Y) & (Z v X)) & (Z → Y).

21. F= (B & (A→C))

22. F= A → B v A&C

23. F= А ↔ (В v C)

24. F = ((X v Y) & (Z v X)) & (Z v Y).

25. F= A → B v A&C

26. F = A & B & C & D.

27. F= А ↔(В v C)

28. F=A& (B→C).

29. F= A ↔ B v A&C

30. F= А ↔ (В v C)

31. F= A → B v A &C

32. F = (A v B) & (B v A v B).

33. F= A v B v A &C

34. F= A & B v A&C

35. F = X & Y ↔ X.

36. F = ((X v Y) & (Z → X)) & (Z ↔ Y).

37. F= A → B &C

38. F = (X → Y) & (Y v X).

39. F= A → B &C

40. F = (A ↔ B) & (B v A &B).

41. F = (X & Y) v Z.

42. F= A & B v A&C

43. F=A& (BvC)

44. F = (X → Y) & (Y ↔ X).

45. F= A → B v A&C

46. F = A & B ↔ C & D.

47. F= А ↔(В v C)

48. F=(X & Y) v (Y & X).

49. Заполните пустые ячейки таблицы истинности:

 

А В С C v A (С v A) =>B
 
 
 
 

 

50. Заполните пустые ячейки таблицы истинности:

 

А В С А B v C А & (В v С)
   
   
   
 
 
 
     
 

 

 

Логические схемы

 

Над возможностями применения логики в технике ученые и инженеры задумывались уже давно. Например, голландский физик Пауль Эренфест (1880 — 1933), кстати несколько лет работавший в России, писал еще в 1910 году: «...Пусть имеется проект схемы проводов автоматической те­лефонной станции. Надо определить: 1) будет ли она правильно функци­онировать при любой комбинации, могущей встретиться в ходе деятель­ности станции; 2) не содержит ли она излишних усложнений. Каждая та­кая комбинация является посылкой, каждый маленький коммутатор есть логическое «или-или», воплощенное в эбоните и латуни; все вместе - сис­тема чисто качественных... «посылок», ничего не оставляющая желать в отношении сложности и запутанности... правда ли, что, несмотря на су­ществование алгебры логики своего рода «алгебра распределительных схем» должна считаться утопией?». Созданная позднее М.А.Гавриловым (1903 - 1979) теория релейно-контактных схем показала, что это вовсе не утопия.

Посмотрим на микросхему. На первый взгляд ничего того, что нас уди­вило бы, мы не видим. Но если рассматривать ее при сильном увеличении она поразит нас своей стройной архитектурой. Чтобы понять, как она ра­ботает, вспомним, что компьютер работает на электричестве, то есть любая информация представлена в компьютере в виде электрических импульсов. Поговорим о них.

С точки зрения логики электрический ток либо течет, либо не течет; электрический импульс есть или его нет; электрическое напряжение есть или его нет... В связи с этим поговорим о различных вариантах управления включением и выключением обыкновенной лампочки (лампочка также работает на электричестве). Для этого рассмотрим электрические контак­тные схемы, реализующие логические операции.

Как известно, любая информация при обработке на компьютере пред­ставляется в двоичной форме, то есть кодируется некоторой после­довательностью 0 и 1. Поэтому упрощенно можно представить работу компьютера как некоторого устройства, производящего обработку двоичных сигналов, соответствующих 0 и 1. Такую обработку в лю­бом компьютере выполняют так называемые логические элементы, из которых составляются логические схемы, выполняющие различ­ные логические операции. Реализация любых логических операций над двоичными сигналами основана на использовании логических элементов трех типов: И, ИЛИ, НЕ.

Логический элемент — это электронное устройство, реализующее одну из логических функций. Рассмотрим указанные три простей­ших логических элемента. В зависимости от типа элемента на его вход подается один или несколько входных сигналов, а на выходе — снимается один выходной сигнал. Названия и условные обозначения этих логических элементов являются стандартными и используются при составлении и описании логических схем компьютеров.

 

 

А —
Логический элемент И (коньюнктор)
&

В —  
   
А —
Логический элемент ИЛИ (дизьюнктор)  
1

В —  
   
А —
Логический элемент НЕ (инвертор)

 

 

 

Почему необходимо уметь строить логические схемы?

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

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

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

 




Поиск по сайту:

©2015-2020 studopedya.ru Все права принадлежат авторам размещенных материалов.