Ast-praktikum

ГОУ ВПО «Алтайский государственный технический университет им. И. И. Ползунова»

Е. В. АСТАХОВА

ВВЕДЕНИЕ В ИНФОРМАТИКУ

Лабораторный практикум

Барнаул

Министерство образования и науки Российской федерации ГОУ ВПО «Алтайский государственный технический университет им. И. И. Ползунова»

Е. В. АСТАХОВА

ВВЕДЕНИЕ В ИНФОРМАТИКУ

Лабораторный практикум

Барнаул 2009

УДК 681.3

Астахова Е. В. Введение в информатику: Лабораторный практикум/ Алт. госуд. технич. ун-т им. И. И. Ползунова.- Барнаул, 2009.- 119 с.

В данном лабораторном практикуме изложено справочно-методическое сопровождение модульного учебного пособия «Введение в информатику» для направления «Информатика и вычислительная техника». Практикум предназначен для выполнения лабораторных работ по дисциплине «Информатика» и может быть использован студентами технических и профессионально-педагогических специальностей очной и дистанционной форм обучения.

ЛАБОРАТОРНАЯ РАБОТА №1

АЛГЕБРА ЛОГИКИ

Цель: Овладение практическими приемами формализации высказываний, решения логических задач.

Задачи:

¾Составление логических выражений.

¾Составление таблиц истинности.

¾Составление логических схем.

Объем работы: 2 часа.

Порядок выполнения: Перед выполнением задания дополнительно ознакомьтесь с материалом раздела 2 Логические основы ЭВМ из Модуля 1.

После выполнения лабораторной работы вы должны

Знать:

¾Базовые логические операции.

¾Аксиомы булевой алгебры.

¾Базовые и элементарные вентили.

Для защиты лабораторной работы вы должны

Уметь:

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

¾Представлять логические выражения в форме таблиц истинности.

¾Реализовывать логические выражения в виде вентильных схем.

Результат:

¾ Навыки решения логических задач различными способами.

4

ЗАДАНИЕ 1. ФОРМАЛИЗАЦИЯ ВЫСКАЗЫВАНИЙ

1. Формализовать высказывания с помощью логических переменных и символов логических операций.

а) Если защитить все лабораторные работы и написать контрольный тест, то можно набрать 75 балов, а это означает возможность получить «автомат».

б) Если защищать лабораторную работу без отчета или не написать контрольный тест, то теряется возможность получить «автомат».

в) Если пропустить лекцию и не написать реферат, то из рейтинга вычитаются 6 баллов, а значит, в итоге можно не дотянуть до «автомата».

г) Если при защите лабораторных блеснуть дополнительными знаниями, то можно заработать дополнительно 5 баллов, а следовательно повысить семестровый рейтинг и может быть заработать «автомат».

д) Если пропускать занятия или вовремя не отрабатывать пропуски, то к концу семестра можно «утонуть» в долгах и не выйти на сессию.

СПРАВОЧНЫЙ МАТЕРИАЛ

Логическое высказывание — это повествовательное предложение, про которое можно однозначно сказать, истинно оно или ложно.

Алгебра логики рассматривает любое высказывание только с позиции его истинности или ложности.

Логические связки — это слова и словосочетания «не», «и», «или», «если …, то», «тогда и только тогда» и т.п.

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

Пример 1. Элементарные высказывания «Иванов — студент», «Иванов — футболист». Связка «И» позволяет получить составное высказывание «Иванов — студент, хорошо играющий в футбол».

Истинность составного высказывания зависит от истинности или ложности элементарных высказываний.

Для обращения к высказываниям им назначают имена.

Пример 2. Обозначим первое высказывание из примера 1 через А, второе — через В. Тогда составное высказывание можно кратко записать как А и В. Здесь А, В — логические переменные, которые могут принимать значения «истина» (1) или «ложь» (0).

Логические связки рассматриваются как операции над логическими высказываниями.

Обозначения логических операций НЕ (черта над высказыванием, ¬) — отрицание (инверсия). Инверсия истинна,

когда высказывание ложно. Например, «6 делится на 2» (А); «6 не делится на 2» (¬А).

И ( , , &) — логическое умножение (конъюнкция). Высказывание А В истинно тогда и только тогда, когда истинны оба элементарных высказывания. Например, для составного высказывания («6 делится на 2 » (А) И «6 делится на 3» (В)) возможны 4 исхода:

1). «6 делится на 2 » И «6 делится на 3» — истинно;

2)«6 делится на 2 » И «6 не делится на 3» — ложно;

3)«6 не делится на 2 » И «6 делится на 3» — ложно;

4)«6 не делится на 2 » И «6 не делится на 3» — ложно;

ИЛИ (+, ) — логическое сложение (дизъюнкция). Высказывание А В ложно тогда и только тогда, когда ложны оба элементарных высказывания. Например, для

5

составного высказывания («6 делится на 2 » (А) И «6 делится на 3» (В)) возможны 4 исхода:

1). «6 делится на 2 » ИЛИ «6 делится на 3» — истинно;

2)«6 делится на 2 » ИЛИ «6 не делится на 3» — истинно;

3)«6 не делится на 2 » ИЛИ «6 делится на 3» — истинно;

4)«6 не делится на 2 » ИЛИ «6 не делится на 3» — ложно;

ЕСЛИ-ТО (→) — импликация. Высказывание А → В ложно тогда и только тогда, когда А истинно, а В ложно. Например, «четырехугольник является квадратом» (А); «данный четырехугольник нельзя вписать в окружность» (В).

Импликацию можно выразить через дизъюнкцию и отрицание А → В = ¬А В.

РАВНОСИЛЬНО (≡, ↔, ~) — эквиваленция (равносильность, двойная импликация). Высказывание А ↔ В истинно тогда и только тогда, когда значения А и В совпадают. Например, «треугольник является прямоугольным» (А) равносильно тому, что «сумма квадратов катетов равна квадрату гипотенузы» (В).

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

А ↔ В = (¬А В) (¬B А).

Замечание. В логических операциях причинно-следственные связи между высказываниями не учитываются. Высказывания могут быть совершенно не связаны по содержанию, рассматривается только их истинность или ложность. Например, «Если студент получил пятерку, то на улице хорошая погода»; «Чтобы получить пятерку

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

ЗАДАНИЕ 2. ЛОГИЧЕСКИЕ ЗАДАЧИ

1.Формализовать логическую задачу. Записать формульное выражение.

2.Решить задачу табличным способом.

Вариант 1. Спор болельщиков о результатах скачек. Петя: Выиграет Алмаз. Пират никогда не приходил первым.

Вася: У Пирата лучше данные — он будет первым. А на Алмаза лучше не ставить. Коля: Алмазу не видать первого места. Победит Пират.

В итоге оказались правы двое из друзей. Кто из лошадей победил в забеге?

Вариант 2. Спор болельщиков о результатах скачек. Петя: Выиграет Алмаз. Пират никогда не приходил первым.

Вася: У Пирата лучше данные — он будет первым. А на Алмаза лучше не ставить. Коля: Алмазу не видать первого места. Победит Пират.

В итоге оказался прав один из друзей. Кто из лошадей победил в забеге?

Вариант 3. Спор болельщиков о результатах скачек. Петя: Выиграет Алмаз или Гранат.

Вася: Первым будет Верный. Коля: Или Верный, или Алмаз.

В итоге оказался прав один из друзей. Кто дал верный прогноз?

6

Вариант 4. Спор болельщиков о результатах скачек. Петя: Выиграет Алмаз или Гранат.

Вася: Первым будет Верный. Коля: Или Верный, или Алмаз.

В итоге оказался прав один из друзей. Кто из лошадей победил в забеге?

СПРАВОЧНЫЙ МАТЕРИАЛ

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

ЗАДАНИЕ 3. АНАЛИЗ ЛОГИЧЕСКОГО ВЫРАЖЕНИЯ

1. Определить наборы значений входных сигналов, при которых выходной сигнал примет значение «ложь».

а) ¬(x y) x б) (x y) ¬x в) x y ¬x

г) ¬(x y) x

СПРАВОЧНЫЙ МАТЕРИАЛ

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

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

(22 = 4): (0,0), (0,1), (1,0), (1,1).

Для формулы с тремя переменными — 8 наборов (23 = 8): (0,0,0), (0,0,1), (0,1,0), (1,0,0), (0,1,1), (1,0,1), (1,1,0), (1,1,1).

ЗАДАНИЕ 4. ПОСТРОЕНИЕ ВЕНТИЛЬНОЙ СХЕМЫ

1. Для логических выражений из задания 3 построить вентильные схемы

7

СПРАВОЧНЫЙ МАТЕРИАЛ

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

Для реализации схем И-НЕ, ИЛИ-НЕ используют графическое изображение инвертора на выходе.

ЗАДАНИЕ 5. ИССЛЕДОВАНИЕ ФОРМУЛЫ

1. С помощью таблиц истинности исследовать формулу на тождественную истинность (ложность).

Вариант 1. ¬(¬x x) y (x y y) Вариант 2. a b (c ¬e d) ¬b Вариант 3. x (y (¬x ¬y))

Вариант 4. ¬((¬x y) (¬y z)) ¬x z

СПРАВОЧНЫЙ МАТЕРИАЛ

Формула называется выполнимой, если она при некоторых значениях переменных принимает значение «истина», а при некоторых — значение «ложь».

Формула называется тождественно истинной (тавтологией), если она при всех значениях переменных принимает значение «истина». Например, формула А ¬А для высказывания «Этот угол прямой или косой».

Формула называется тождественно ложной (противоречием), если она при всех значениях переменных принимает значение «ложь». Например, формула А ¬А для высказывания «Это дерево самое высокое в саду, но есть деревья выше».

8