Discrete Mathematics
Discrete
Mathematics
Chapter
01
The
Foundations:
Logic
and
Proofs
Lectures
Reference
2
Compound
Propositions
Logic
and
Bit
Operations
•
Computers represent information
using
bits
.
A
bit
is a
symbol with two
possible
values,
namely,
0 (zero) and 1
(one).
3
Compound
Propositions
(
2
)
Computer
Bit
Operations
•
We
will
also
use
the
notation
OR,
AND,
and
XOR
for
the
operators
∨
,
𝖠
,
and
⊕
,
as
is
done
in
various
programming
languages.
4
Bit
Strings
•
Information is often represented
using bit strings,
which
are lists of zeros and ones. When this is done, operations
on
the
bit
strings
can
be
used
to
manipulate
this
information.
Compound
Propositions
(3)
5
Example
•
Find
the
bitwise
OR,
bitwise
AND,
and
bitwise
XOR
of
the
bit
strings
01
1011
0110
and
11
0001
1101
Compound
Propositions
(
4
)
6
Applications
of
Propositional
Logic
(1/13)
1-
Translating
English Sentences.
2-
System
Specifications.
3
Boolean
Searches.
4
Logic
Puzzles.
5
Logic
Circuits.
7
Applications
of
Propositional
Logic
(2/13)
Translating
English
Sentences
•
There are
many
reasons to translate English sentences
into
expressions
involving
propositional
variables
and
logical
connectives.
In
particular,
English
(and
every
other human language) is often ambiguous.
Translating
sentences into compound statements (and other types of
logical
expressions,
which we will
introduce
later in
this
chapter)
removes
the
ambiguity.
8
Applications
of
Propositional
Logic
(3/13)
9
Example
1
You
can
access
the
Internet
from
campus
only
if
you
are
a
computer
science
major
or
you
are
not
a
student.
Applications
of
Propositional
Logic
(4/13)
10
Example
1
You
can
access
the
Internet
from
campus
only
if
you
are
a
computer
science
major
or
you
are
not
a
student.
Let
𝑝
,
𝑞
and
𝑟
be the
proposi
t
ions:
𝑝:
You
can
access
the
Internet
from
campus.
𝑞:
You
are
a
computer
science
major.
𝑟:
You
are
a
student.
Applications
of
Propositional
Logic
(4/13)
11
Example
1
(
You
can
access
the
Internet
from
campus
)
only
if
(
you
are
a
computer
science
major
or
you are
not
a
student
)
.
𝑝
→
𝑞
Let
𝑝
,
𝑞
and
𝑟
be the
proposi
t
ions:
𝑝:
You
can
access
the
Internet
from
campus.
𝑞:
You
are
a
computer
science
major.
𝑟:
You
are
a
student.
Applications
of
Propositional
Logic
(5/13)
12
Example
1
(
You
can
access
the
Internet
from
campus
)
only
if
(
you
are
a
computer
science
major
or
you are
not
a
student
)
.
𝑝
→
𝑞
Let
𝑝
,
𝑞
and
𝑟
be the
proposi
t
ions:
𝑝:
You
can
access
the
Internet
from
campus.
𝑞:
You
are
a
computer
science
major.
𝑟:
You
are
a
student.
The
sentence
can
be
represented
by
logic
as
𝑝
→
(𝑞
∨
¬𝑟)
Applications
of
Propositional
Logic
(6/13)
13
Example
2
The
automated
reply
cannot
be
sent
when
the
file
system
is
full.
Applications
of
Propositional
Logic
(7/13)
14
Example
2
The
automated
reply
cannot
be
sent
when
the
file
system
is
full.
Let
𝑝
and
𝑞
be
the
propositions:
𝑝:
The
automated
reply
can
be
sent
.
𝑞:
The
file
system
is
full.
𝑝
→
𝑞
Applications
of
Propositional
Logic
(8/13)
15
Example
2
(
The
automated
reply
cannot
be
sent
)
when
(
the
file
system
is
full.
)
Let
𝑝
and
𝑞
be
the
propositions:
𝑝:
The
automated
reply
can
be
sent
.
𝑞:
The
file
system
is
full.
The
sentence
can
be
represented
by
logic
as
𝑞
→
¬𝑝
𝑝
→
𝑞
Explore the foundations of logic and proofs in discrete mathematics, focusing on compound propositions, bit operations, and applications of propositional logic. Learn about how computers use bits for information representation and manipulation, and delve into translating English sentences into logical expressions. Discover the bitwise operations of OR, AND, and XOR on bit strings, along with real-world examples showcasing the applications of propositional logic.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Discrete Mathematics Chapter 01 The Foundations:Logic and Proofs
Compound Propositions Logic and Bit Operations Computers represent information using bits. A bit is a symbol with two possible values, namely, 0 (zero) and 1 (one). 3
Compound Propositions (2) Computer Bit Operations We will also use the notation OR, AND, and XOR for the operators , ?, and , as is done in various programming languages. 4
Compound Propositions (3) Bit Strings Information is often represented using bit strings, which are lists of zeros and ones. When this is done, operations on the bit strings can be used to manipulate this information. 5
Compound Propositions (4) Example Find the bitwise OR, bitwiseAND, and bitwise XOR of the bit strings 01 1011 0110 and 11 0001 1101 6
Applications of Propositional Logic (1/13) 1- Translating English Sentences. 2- System Specifications. 3 Boolean Searches. 4 Logic Puzzles. 5 Logic Circuits. 7
Applications of Propositional Logic (2/13) Translating English Sentences There are many reasons to translate English sentences into expressions involving propositional variables and logical connectives. In particular, English (and every other human language) is often ambiguous. Translating sentences into compound statements (and other types of logical expressions, which we will introduce later in this chapter) removes the ambiguity. 8
Applications of PropositionalLogic (3/13) Example 1 You can access the Internet from campus only if you are a computer science major or you are not a student. 9
Applications of PropositionalLogic (4/13) Example 1 You can access the Internet from campus only if you are a computer science major or you are not a student. Let ?,? and ? be the propositions: ?: You can access the Internet from campus. ?: You are a computer science major. ?: You are a student. 10
Applications of PropositionalLogic (4/13) Example 1 (You can access the Internet from campus) only if (you are a computer science major or you are not a student). Let ?,? and ? be the propositions: ? ? ?: You can access the Internet from campus. ?: You are a computer science major. ?: You are a student. 11
Applications of PropositionalLogic (5/13) Example 1 (You can access the Internet from campus) only if (you are a computer science major or you are not a student). Let ?,? and ? be the propositions: ? ? ?: You can access the Internet from campus. ?: You are a computer science major. ?: You are a student. The sentence can be represented by logic as ? (? ?) 12
Applications of PropositionalLogic (6/13) Example 2 The automated reply cannot be sent when the file system is full. 13
Applications of PropositionalLogic (7/13) Example 2 The automated reply cannot be sent when the file system is full. Let ? and ? be the propositions: ? ? ?: The automated reply can be sent . ?: The file system is full. 14
Applications of PropositionalLogic (8/13) Example 2 (The automated reply cannot be sent) when (the file system is full.) Let ? and ? be the propositions: ? ? ?: The automated reply can be sent . ?: The file system is full. ? ? The sentence can be represented by logic as 15
