Propositions Flashcards
is a declarative sentence (that is, a sentence that declares a fact) that is either
true or false, but not both.
proposition
We use letters to denote_____________________, that is, variables
that represent propositions, just as letters are used to denote numerical variables
propositional variables(or sentential variables)
The conventional letters used for propositional variables are
p, q, r, s, …
a proposition is true, denoted by T, if it is a true proposition, and the truth value of a proposition is false, denoted by F, if it is a false proposition
truth value
Propositions that cannot be expressed in terms of simpler
propositions are called
atomic propositions.
The area of logic that deals with propositions is called the
propositional calculus or propositional logic
It was first developed systematically by the Greek philosopher _____________ more than
2300 years ago.
Aristotle
These methods were discussed by the English mathematician George Boole in
1854 in his book
The Laws of Thought.
New propositions, called ___________________________ , are formed
from existing propositions using __________________________
compound propositions, logical operators.
Let p be a proposition. The negation of p, denoted by ¬p (also denoted by p), is the statement
“It is not the case that p.”
The proposition ¬p is read “not p.” The truth value of the negation of p, ¬p, is
the opposite
of the truth value of p.
The notation for the negation operator is not standardized. Although ¬p and p are the
most common notations used in mathematics to express the negation of p, other notations you
might see are
∼p, −p, p′
, Np, and !p.
The negation of a proposition can also be considered the result of the operation of the
negation operator on a proposition
logical operators that are used to form
new propositions from two or more existing propositions
connectives.
The conjunction of p and q, denoted by p ∧ q, is the proposition
“p and q.” The conjunction p ∧ q is
true when both p and q are true and is false otherwise
The disjunction of p and q, denoted by p ∨ q, is the proposition
“p or q.” The disjunction p ∨ q is false when
n both p and q are false and is true otherwise.
The use of the connective or in a disjunction corresponds to one of the two ways the word
or is used in English, namely, as an
inclusive or
The exclusive or of p and q, denoted by p ⊕ q (or p XORq), is
the proposition that is true when
exactly one of p and q is true and is false otherwise.
“Students who have taken calculus or computer science, but not both, can enroll in this
class.”
e exclusive or
The exclusive or of p and q, denoted by p ⊕ q, is the proposition
that is true when exactly
one of p and q is true and is false otherwise.
The conditional statement p → q is the proposition “if p, then
q.” The conditional statement p → q is false when p is true and q is false, and true otherwise.
In the conditional statement p → q, p is called the
hypothesis (or antecedent or premise)
and q is called the conclusion (or consequence).
The statement p → q is called a conditional statement because
p → q asserts that q is true
on the condition that p holds
A conditional statement is also called an
implication
Most programming languages contain statements such as
if p then S,
The proposition q → p
is called the
converse of p → q
is the proposition ¬q → ¬p.
contrapositive of p → q
The proposition ¬p → ¬q is called the
inverse of p → q
When two compound propositions always have the same truth value we call them
equivalent
” The biconditional statement p ↔ q is true when
p and q have the same truth
values, and is false otherwise. Biconditional statements are also called bi-implications
is a symbol with two possible values, namely,
0 (zero) and 1 (one)
bit
A variable is called a
Boolean variable
correspond to the logical connectives
computer bit operations
is a sequence of zero or more bits.
bit string
The __________ of this string is the number of _______
in the string.
length, bits
We define the bitwise OR, bitwise AND, and
bitwise XOR of two strings of the same length to be
the strings that have as their bits the OR,
AND, and XOR of the corresponding bits in the two strings, respectively
