Mathematical Structures I Class Notes

Logic & Propositions

, Logic and Propositions


Definition: A sentence that is either true or false, but not both, is called a proposition. Propositions are
also called statements. (Throughout the lecture, the terms “proposition” and “statement” will be used
interchangeably.)


Examples of Propositions:
 Our campus is in Fullerton.
 Today is Tuesday.
 2+5=9
 2<5
 They all like pizza.
 The car is blue.
 It is snowing outside.


The following are not propositions:
 Is today Tuesday?
 What time is it?
 Stop!
 Let’s study.




Operators

Main Ideas: Consider the propositions 𝑝: 𝐼 ℎ𝑎𝑣𝑒 𝑎 𝑝𝑒𝑛𝑛𝑦 𝑞: 𝐼 ℎ𝑎𝑣𝑒 𝑎 𝑞𝑢𝑎𝑟𝑡𝑒𝑟 . We can form new
propositions using operators such as the negation, conjunction, and disjunction.

1. The negation of p, denoted 𝑝̅ , means ____________.
not P


 𝑝̅ is pronounced “p bar” or “the negation of p”

 In this case, 𝑝̅ in words is ___________________________________.
I do not have a
penny

 The truth values are defined like this:


F

, a
2. The conjunction, denoted 𝑝 ∧ 𝑞 , means ______________________.
pand
 I have both
The statement “I have a penny and I have a quarter” is true if and only if ____________________.
 The truth values are defined like this:
pqp1q
T
I
F
P q
 Logically, the word “but” means “and”. The statement “I
--
have a penny but not a quarter” can be
written symbolically as ____________.
p1q




3. The disjunction, denoted 𝑝 ∨ 𝑞, means _______________.
por g
 This is the inclusive “or”, so it means “one, the other, or both”.
 The statement “I have a penny or I have a quarter” is true unless ___________________________.
I have neither
 The truth values are defined like this:
PqpVq



=
4. Write the negation of the statement: “I
I do not have a
--

penny
" not
heave
have a penny or I have a quarter.”
and do a quarter

result the :
negation of pVq is 5G




Operator Precedence: Without parentheses, we evaluate ∧ before ∨.
For instance, 𝑝 ∧ 𝑟̅ ∨ 𝑞 ∧ 𝑝 means (𝑝 ∧ 𝑟̅) ∨ (𝑞 ∧ 𝑝).


Important Remark: Logic is concerned with the form of propositions and the relation of propositions to
each other, not with the subject matter itself. In ordinary language, propositions that are combined are
usually related, but logically that is not necessary.

, Finding Truth Values

Vq
Example: What does a truth table really mean? Consider this statement: “--
7 < 3 or this is math 170A”.
The truth value of this proposition is…
true ,
since false V true is true




Example: Write the truth table for the proposition (𝑝 ∧ 𝑞) ∨ 𝑞̅




I
P9p19(a)v
TTT T

T



+
T

F
F




Example: Find the truth value of (𝑞 ∧ 𝑟) ∧ (𝑞̅ ∨ 𝑝) given that p is false, q is true, and r is true.

(T15)(vF)
T1(F VF)
TMF

F