uzluga.ru
добавить свой файл


Алгебра логики


Логика

  • Логика

  • — это наука о формах и способах мышления.



Основными формами абстрактного мышления являются :

  • 1.Понятие

  • 2.Высказывание

  • 3.Умозаключение



Понятие

  • Понятиеэто форма мышления, фиксирующая основные, существенные признаки объекта.

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



Какие известные вам понятия определяются следующими предложениями:

    • Какие известные вам понятия определяются следующими предложениями:
  • 1)      группа слов, которая выражает законченную мысль;

  • 2)      расстояние, преодолеваемое за единицу времени;

  • 3)      часть прямой, ограниченная с двух сторон;

  • 4)      многоугольник с наименьшим числом сторон;

  • 5)      последовательность команд, которую выполняет компьютер в процессе обработки данных;

  • 6)   система хранения файлов и организации каталогов.



Отношения между объемами понятий. Диаграммы Эйлера-Венна.

  •       тождество

  • пример: А= «столица Франции»

  • В= « Париж»       



Отношения между объемами понятий. Диаграммы Эйлера-Венна.

  • подчинение

  • пример:

  • А=«журналы»

  • В=«Информатика в школе»

  •   исключение

  • пример:

  • А=«комплектующие компьютера»

  • В=«школьные принадлежности»

  • ·    



Отношения между объемами понятий. Диаграммы Эйлера-Венна.

  • пересечение

  • пример:

  • А=«сотрудники»

  • В = «академики»

  • соподчинение

  • пример:

  • А=«мальчики» и В=«девочки»

  • С=«школьники»



По аналогии с приведенными в таблице примерами для каждого типа отношений между понятиями придумайте 2-3 собственных примера.



Высказывание

  • Высказывание это форма мышления, в которой что-либо утверждается или отрицается о предметах, признаках или их отношениях.

  • Высказывание может быть либо истинно, либо ложно.

  • Примеры: Буква «а» - гласная.

  • Дважды два – четыре.



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

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

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

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

  • Париж – столица Англии.

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

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



Умозаключение

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

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

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



Алгебра высказываний

  • Алгебра высказываний



Высказывание может быть:

  • Высказывание может быть:

  • простым;

  • составным.



  • Логическая переменная – это простое высказывание, содержащее только одну мысль. Ее символическое обозначение – латинская буква (А, В, С и т.д.)

  • А = {Аристотель - основоположник логики}

  • В = {На яблонях растут бананы}.

  •   Истинному высказыванию ставится в соответствие 1, ложному — 0.

  • Таким образом, А = 1, В = 0.



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



Какие из следующих предложений являются истинными, а какие ложными высказываниями?

  • Какие из следующих предложений являются истинными, а какие ложными высказываниями?

  • 1) Город Париж — столица Франции.

  • 2) Число 2 является делителем числа 7.

  • 3) 3 + 5 = 2 * 4.

  • 4) 2 + 6 > 10.

  • 5) Сканер — это устройство, которое может напечатать на бумаге то, что изображено на экране компьютера.

  • 6) II + VI > VIII.

  • 7) Сумма чисел 2 и 6 больше числа 8.

  • 8) Мышка — устройство ввода информации.



  • Логические операции

  • алгебры высказываний



  Логическая операция КОНЪЮНКЦИЯ :

  •   Логическая операция КОНЪЮНКЦИЯ :

  • в естественном языке соответствует союзу и;

  • обозначение: &;

  • в языках программирования обозначение: and;

  • иное название: логическое умножение.



Логическая операция ДИЗЪЮНКЦИЯ:

  • Логическая операция ДИЗЪЮНКЦИЯ:

  • в естественном языке соответствует союзу или;

  • обозначение: V ;

  • в языках программирования обозначение: or;

  • иное название: логическое сложение.



Логическая операция ИНВЕРСИЯ :

  • Логическая операция ИНВЕРСИЯ :

  • в естественном языке соответствует словам "Неверно, что... " и частице не;

  • обозначение: ¯A ;

  • в языках программирования обозначение: not;

  • иное название: отрицание.



  Логическая операция ИМПЛИКАЦИЯ :

  •   Логическая операция ИМПЛИКАЦИЯ :

  • в естественном языке соответствует обороту

  • Если ..., то ...;

  • обозначение: →, ;

  • иное название: логическое следование.



  Логическая операция ЭКВИВАЛЕНЦИЯ :

  •   Логическая операция ЭКВИВАЛЕНЦИЯ :

  • в естественном языке соответствует оборотам речи тогда и только тогда и в том и только в том случае;

  • обозначение: , ~ ;

  • иное название: равнозначность.



Приоритеты логических операций

  • действия в скобках;

  • инверсия;

  • конъюнкция &;

  • дизъюнкция V;

  • импликация ;

  • эквиваленция .



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

  • Логическое выражение – это составное высказывание, выраженное в виде формулы логических переменных и логических операций.

  • Значением логического выражения могут быть только ИСТИНА или ЛОЖЬ.



Решение задач

  • Пример 1. Определите истинность простых высказываний:

  • А = {Принтер – устройство вывода информации},

  • В = {Процессор – устройство хранения информации},

  • С = {Монитор – устройство вывода информации},

  • D = {Клавиатура – устройство обработки информации}.

  •  Пример 2. Определите истинность составного высказывания:

  • ( ¯А &¯B ) & (C V D)

  •        



Решение

  • На основании знания устройства компьютера устанавливаем истинность простых высказываний:

  • А = 1, В = 0, С = 1, D = 0.

  •         Определим сначала истинность составного высказывания, используя таблицы истинности логических операций:

  • (¯1& ¯0 ) & (1 V 0) = (0&1) & (1 V 0) = 0&1 = 0



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

  • Решение: проанализируем составное высказывание. Оно состоит из трех простых высказываний:

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

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

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

  • Тогда логическое выражение примет вид:

  • F=A&(B→C)



Пример 3. Какие из высказываний А, В, С должны быть истинны и какие ложны, чтобы было ложно логическое выражение ((A V В) & В)  С.

  • Пример 3. Какие из высказываний А, В, С должны быть истинны и какие ложны, чтобы было ложно логическое выражение ((A V В) & В)  С.



Решение

  • Импликация ложна на единственном наборе (1 0). Значит, С = 0, ((A V В) & В) = 1.

  •         Конъюнкция истинна на единственном наборе (1 1). Значит, В = 1 и (A V В) = 1.

  •         Дизъюнкции истинна при наборах (1 0) и (1 1).

  •         Следовательно, существуют два набора, удовлетворяющих условию задачи: (А = 0, В = 1, С = 0) и (А = 1, В = 1, С = 0).  



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

    • Пример 4.Среди следующих высказываний укажите составные; выделите в них простые, обозначив каждое их них буквой; запишите с помощью логических операций каждое составное высказывание.
  • 1)      Число 376 четное и трехзначное.

  • 2)      Неверно, что Солнце движется вокруг Земли.

  • 3)      Земля имеет форму шара.

  • 4)      На уроке математики старшеклассники отвечали на вопросы учителя и писали самостоятельную работу.

  • 5)      Если сумма цифр числа делится на 3, то число делится на 3.

  • 6)      Число 15 делится на 3 тогда и только тогда, когда сумма цифр числа 15 делится на 3.



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

    • Пример 5. Найдите значения логических выражений:
  •     а) (1V1)V(1V0);

  •     б) ((1V0)V1)V1;

  •     в) (0V1)V(1V0);

  •     г) (0&1)&1;

  •     д) 1&(1&1)&1;

  •     е) ((1V0)&(1&1))&(0V1);

  •     ж) ((1&0)V(1&0))V1;

  •     з) ((1&1)V0)&(0V1);

  •     и) ((0&0)V0)&(1V1).  



Пример 6. Даны два высказывания:

    • Пример 6. Даны два высказывания:
  • А = {2 * 2 = 4}, В = {2 * 2 = 5}.

  • Очевидно, что А = 1, В = 0.

  • Какие из высказываний а)—е) истинны?

  • а)¯A; б) ¯B ;

  • в) А & В; г) A V В;

  • д) АВ; е) АВ.  



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

  • А является max(А, В, С);

  • Если Х делится на 2, то оно четное.

  • Хотя бы одно из чисел К, L, М положительно.

  • Все числа Х, У, Z равны 12.

  • Хотя бы одно из чисел А, В, С отрицательно.



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

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



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

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



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

  • Выяснить кол-во строк в таблице: 2n, где n – кол-во переменных;

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

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

  • Построить таблицу, указывая названия столбцов;

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



Решение примеров

  • Пример 1. Для формулы

  • A&(B V ¯B & ¯C)

  • построить таблицу истинности алгебраически и с использованием электронных таблиц.





Логические законы и правила преобразования логических выражений

  • Логические законы и правила преобразования логических выражений



1. Закон двойного отрицания

  • _

  • _

  • А = A



2. Переместительный (коммутативный) закон:

  • — для логического сложения:

  • А V B = B V A

  • — для логического умножения:

  • A&B = B&A



3. Сочетательный (ассоциативный) закон:

  • — для логического сложения:

  • (A V B) V C = A V (B V C)

  • — для логического умножения:

  • (A&B)&C = A&(B&C)



4. Распределительный (дистрибутивный) закон:

  • — для логического сложения:

  • (A V B)&C = (A&C) V (B&C)

  • — для логического умножения:

  • (A&B) V C = (A V C)&(B V C)



5. Закон общей инверсии (законы де Моргана):

  • _____ _ _

  • A V B = A & B

  •   _____ _ _

  • A & B = A V B

  • ______ __

  • (А → B) = A & B

  • __

  • A → B = A V B



6. Закон идемпотентности

  • — для логического сложения:

  • A V A = A

  • — для логического умножения:

  • A&A = A



7. Законы исключения констант:

  • — для логического сложения:

  • A V 1 = 1; A V 0 = A

  • — для логического умножения:

  • A & 1 = A; A & 0 = 0



8. Закон противоречия:

  • _

  • A & A = 0



9. Закон исключения третьего:

  • _

  • A V A = 1



10. Закон поглощения:

  •   — для логического сложения:

  • A V (A&B) = A

  •   — для логического умножения:

  • A&(A V B) = A



11. Закон исключения (склеивания):

  • — для логического сложения:

  • _

  • (A & B) V (A & B) = B

  • — для логического умножения:

  • _

  • (A V B) & (A V B) = B



12. Закон контрапозиции (правило перевертывания):

  • (A <=> B) = (B <=> A)



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

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

  • Пример: упростить логическое выражение

  • _____________

  • _____

  • F= (A V B) → (B V C)

  • Ответ: B V A & C



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

  • Разнообразие логических задач очень велико. Способов их решения тоже немало. Но наибольшее распространение получили следующие три способа решения логических задач:

    • средствами алгебры логики;
    • табличный;
    • с помощью рассуждений.


Решение логических задач средствами алгебры логики

  • Обычно используется следующая схема решения:

  • 1. изучается условие задачи; 2. вводится система обозначений для логических высказываний; 3. конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи; 4. определяются значения истинности этой логической формулы; 5. из полученных значений истинности формулы определяются значения истинности введённых логических высказываний, на основании которых делается заключение о решении



Пример 1. Трое друзей, болельщиков автогонок "Формула-1", спорили о результатах предстоящего этапа гонок.

  • Пример 1. Трое друзей, болельщиков автогонок "Формула-1", спорили о результатах предстоящего этапа гонок.

  • — Вот увидишь, Шумахер не придет первым, — сказал Джон. Первым будет Хилл.

  • — Да нет же, победителем будет, как всегда, Шумахер, — воскликнул Ник. — А об Алези и говорить нечего, ему не быть первым.

  • Питер, к которому обратился Ник, возмутился:

  • — Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину.

  • По завершении этапа гонок оказалось, что каждое из двух предположений двоих друзей подтвердилось, а оба предположения третьего из друзей оказались неверны. Кто выиграл этап гонки?



Решение. Введем обозначения для логических высказываний:

  • Решение. Введем обозначения для логических высказываний:

  • Ш — победит Шумахер; Х — победит Хилл; А — победит Алези.

  • Реплика Ника "Алези пилотирует самую мощную машину" не содержит никакого утверждения о месте, которое займёт этот гонщик, поэтому в дальнейших рассуждениях не учитывается.

  • Зафиксируем высказывания каждого из друзей:

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

  • Высказывание истинно только при Ш=1, А=0, Х=0.

  • Ответ. Победителем этапа гонок стал Шумахер.



Решение логических задач табличным способом

  • Пример 2. В симфонический оркестр приняли на работу трёх музыкантов: Брауна, Смита и Вессона, умеющих играть на скрипке, флейте, альте, кларнете, гобое и трубе.

  • Известно, что:

  • 1. Смит самый высокий; 2. играющий на скрипке меньше ростом играющего на флейте; 3. играющие на скрипке и флейте и Браун любят пиццу; 4. когда между альтистом и трубачом возникает ссора, Смит мирит их; 5. Браун не умеет играть ни на трубе, ни на гобое.

  • На каких инструментах играет каждый из музыкантов, если каждый владеет двумя инструментами?



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

  • Решение. Составим таблицу и отразим в ней условия задачи, заполнив соответствующие клетки цифрами 0 и 1 в зависимости от того, ложно или истинно соответствующее высказывание.

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

  • Из условия 4 следует, что Смит не играет ни на альте, ни на трубе, а из условий 3 и 5, что Браун не умеет играть на скрипке, флейте, трубе и гобое. Следовательно, инструменты Брауна — альт и кларнет. Занесем это в таблицу, а оставшиеся клетки столбцов "альт" и "кларнет" заполним нулями:





Пример 2. Три одноклассника — Влад, Тимур и Юра, встретились спустя 10 лет после окончания школы. Выяснилось, что один из них стал врачом, другой физиком, а третий юристом. Один полюбил туризм, другой бег, страсть третьего — регби.

  • Пример 2. Три одноклассника — Влад, Тимур и Юра, встретились спустя 10 лет после окончания школы. Выяснилось, что один из них стал врачом, другой физиком, а третий юристом. Один полюбил туризм, другой бег, страсть третьего — регби.

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

  • Забавно, но у двоих из друзей в названиях их профессий и увлечений не встречается ни одна буква их имен.

  • Определите, кто чем любит заниматься в свободное время и у кого какая профессия.



Решение. Здесь исходные данные разбиваются на тройки (имя — профессия — увлечение).

  • Решение. Здесь исходные данные разбиваются на тройки (имя — профессия — увлечение).



Решение логических задач с помощью рассуждений

  • Пример 3. Вадим, Сергей и Михаил изучают различные иностранные языки: китайский, японский и арабский. На вопрос, какой язык изучает каждый из них, один ответил: "Вадим изучает китайский, Сергей не изучает китайский, а Михаил не изучает арабский". Впоследствии выяснилось, что в этом ответе только одно утверждение верно, а два других ложны. Какой язык изучает каждый из молодых людей?



Решение. Имеется три утверждения:

  • Решение. Имеется три утверждения:

  • 1. Вадим изучает китайский; 2. Сергей не изучает китайский; 3. Михаил не изучает арабский. Если верно первое утверждение, то верно и второе, так как юноши изучают разные языки. Это противоречит условию задачи, поэтому первое утверждение ложно.

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

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

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



Решение задач с помощью таблицы

  • Решение задач с помощью таблицы

  • ЗАДАЧА. Пятеро одноклассников – Аня, Саша, Лена, Вася и Миша – стали победителями олимпиад школьников по физике, математике, информатике, литературе и географии. Известно, что:

  • Победитель олимпиады по информатике учит Аню и Сашу работе на компьютере;

  • Лена и Вася тоже заинтересовались информатикой;

  • Саша всегда побаивался физики;

  • Лена, Саша и победитель и победитель олимпиады по литературе занимаются плаванием;

  • Саша и Лена поздравили победителя олимпиады по математике;

  • Аня сожалеет о том, что у нее остается мало времени на литературу.

  • Победителем какой олимпиады стал каждый из этих ребят?



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

  • Решение задач средствами алгебры логики

  • ЗАДАЧА. Виновник ночного дорожно-транспортного происшествия скрылся с места аварии. Первый из опрошенных свидетелей сказал работникам ГАИ, что марка машины нарушителя – «Жигули», первая цифра номера машины – единица. Второй свидетель сказал, что машина была марки «Москвич», а номер начинался с семерки. Третий свидетель заявил, что машина была иностранная, номер начинался не с единицы. А доброжелатель по телефону сообщил, что каждый из свидетелей правильно указал либо марку машины, либо первую цифру номера. Помогите следствию, определите марку машины и первую цифру номера?



Построение логических схем

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



Схема 1

  • Оба контакта в положении «вкл». Тогда ток через лампочку идет и она горит.

  • Первый контакт в положении «вкл», второй – в положении «выкл». Ток не идет, лампочка не горит.

  • Обратная ситуация. Лампочка не горит.

  • Оба контакта в положении «выкл». Тока нет. Лампочка не горит.

  • Вывод: первая схема действительно реализует логическую операцию «И»



Схема 2

  • Оба контакта в положении «вкл». Тогда ток через лампочку идет и она горит.

  • Первый контакт в положении «вкл», второй – в положении «выкл». Ток идет, лампочка горит.

  • Обратная ситуация. Лампочка горит.

  • Оба контакта в положении «выкл». Тока нет. Лампочка не горит.

  • Вывод: вторая схема действительно реализует логическую операцию «ИЛИ»



Схема 3

  • В этом устройстве в качестве переключателя используется автоматический ключ Когда тока на нем нет, пластинка замыкает контакты и лампочка горит. Если на ключ подать напряжение, то вследствие явления электромагнитной индукции пластинка прижимается и цепь размыкается. Лампочка не горит.

  • Вывод: вторая схема действительно реализует логическую операцию «НЕ»



Правила построения логических схем

  • Определить число логических переменных.

  • Определить количество базовых логических операций и их порядок.

  • Изобразить для каждой логической операции соответствующий ей вентиль.

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



Пример 1.

  • Составить логическую схему для выражения F = X v Y & X,

  • где Х = истина, Y = ложь.



Пример 2

  • Составить логическую схему для

  • _____

  • выражения F = X & Y v (Y v X),

  • где Х = 1, Y = 0.



Логические основы компьютера

  • Логические основы компьютера



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

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



          

  •           

  • Из логических элементов путем их комбинации строятся основные схемы компьютера:

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

  • Регистр - совокупность триггеров, предназначенных для хранения числа в двоичном коде.

  • Сумматор - устройство обеспечивающее суммирование двоичных чисел с учетом переноса из предыдущего разряда.



Что такое триггер?

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