View source for SP18:Lecture 4 Logic



In this lecture, we will examine several forms of [[proposition]]; for each we
will discuss how to prove it, how to disprove it, and how to use it in a proof
(if it is already known to be true).


* Reading: [[MCS]] chapter 1
* [http://www.cs.cornell.edu/courses/cs2800/2017fa/lectures/lec03-proofs.html Last semester's notes]
* [[File:Lec04-board.pdf]]


= Propositions =

{{:Proposition}}

= Combining propositions =

If you have [[proposition]]s <math>P</math>, <math>Q</math>, and <math>R</math>, you
can combine them in natural ways to form new propositions.  The structure of
these combined propositions can help you determine how to prove them, or how to
use them if you know they are true.  We will examine several of these combined
propositions today; we will summarize them in [[SP18 Lecture 5 Functions|the
next lecture]] in a [[table of proof techniques]].

You can view this overview as a guide to [[do what it says, use what you know|
doing what it says, and using what you know]].  At any point in a proof, there
is a current set of [[proposition|facts]] that you've already proven (or
assumed), and there is a particular [[proposition]] that you are [[want to show|trying
to show]].  You can apply these strategies to those propositions to make
progress.

== Note on notation ==

We are introducing symbols for words like "and", "or", and "not".  These symbols
are helpful when talking about logic itself, but I find they make proofs much
harder to read, so I avoid them when writing proofs.  This is a matter of style.

== P and Q ==

{{:and}}

== P or Q ==

{{:or}}

== P is false ==

{{:not}}

== For all x, P ==

{{:for all}}