Schedule

We discussed some aspects of the syllabus and answered some questions regarding the course.

• Course Content
• Course Objectives
• Assignments and Standards

• A logic riddle
• Sudoku rules and hints at basic techniques

Explained the game \( \operatorname{Nim}(n; \{1,2,3\}) \).

Setup

Two players make a pile of \( n \) stones and decide who will go first.

Gameplay

Players alternate picking up \( 1 \), \( 2 \), or \( 3 \) stones from the pile.

Win Condition

The player to pick up the last stone loses.

Discussed what makes a "logical argument".

Statement

A sentence which is either true or false, and not both.

Argument

Sequence of premises followed by a conclusion.

Premise

Statement that is assumed for the sake of the argument.

Conclusion

Statement claimed to follow from the premises.

Valid

An argument form is valid when it's conclusion always follows from the premises, regardless of the information content of the statements.

Sound

An argument is sound when it's premises are true.

We noticed that the definition of statement precludes things that are "up for debate" as statements. This is because we want the simplest model for good reasoning possible. It will also allow us to analyze statements in a purely symbolic way, i.e., without worrying about the meaning!

Discussed what makes a statement, and how to build up new statements from old ones. We agreed to use statement variables, i.e., letters to stand in for statements.

Negation

"not A", "it is not the case that A", "\( \lnot A \)"

Conjunction

"both A and B", "A but B", "\( A \wedge B \)"

Disjunction

"either A or B", "\( A \vee B \)"

Implication

"if A, then B", "A implies B", "\( A \rightarrow B \)"

Justification

"A therefore B", "A so B", "B because A"

We agreed that "Justification" is a bit different from the others somehow, so we can't analyze justification in the same way as the others. In fact, how to understand this one is a question outside of logic, so we won't discuss it further.

• Ambiguity in natural language.
• Using a dictionary to translate from English to symbolic logic.
• Using a dictionary to (reverse) translate from symbolic logic to English.

Constructed (with reasons!) the truth tables for the usual logical connectives. These are summarized in the single table below.

\begin{array}{c|c|c|c|c|c} P & Q & \lnot P & P \wedge Q & P \vee Q & P \rightarrow Q \\ \hline T & T & F & T & T & T \\ T & F & F & F & T & F \\ F & T & T & F & T & T \\ F & F & T & F & F & T \end{array}

In addition, we did several examples constructing truth tables for symbolic statements.

More on truth tables, including analysis of statements with three or more atomic statements.

Statements are logically equivalent when they have the same main column in their truth table. We think of this as saying that the two statements have the same "truth content", or that they "mean roughly the same thing".

The next lectures will be spent hunting for common and useful logical equivalences.

Below, \( A \), \( B \), and \( C \) denote arbitrary statements, and \( T \) and \( F \) denote the truth values.

Name	Formula
Associativity	\( A \wedge (B \wedge C) \equiv (A \wedge B) \wedge C \)
	\( A \vee (B \vee C) \equiv (A \vee B) \vee C \)
Commutativity	\( A \wedge B \equiv B \wedge A\)
	\( A \vee B \equiv B \vee A \)
Idempotence	\( A \vee A \equiv A \)
	\( A \wedge A \equiv A \)
Absorption	\( A \vee T \equiv T \)
	\( A \vee F \equiv A \)
	\( A \wedge T \equiv A \)
	\( A \wedge F \equiv F \)
Negated Value	\( \lnot T \equiv F \)
	\( \lnot F \equiv T \)
Distributivity	\( A \wedge (B \vee C) \equiv (A \wedge B) \vee (A \wedge C) \)
	\( A \vee (B \wedge C) \equiv (A \vee B) \wedge (A \vee C) \)
Double Negation	\( \lnot (\lnot A) \equiv A \)
DeMorgan's Laws	\( \lnot (A \wedge B) \equiv (\lnot A) \vee (\lnot B) \)
	\( \lnot (A \vee B) \equiv (\lnot A) \wedge (\lnot B) \)
Material Implication	\( A \rightarrow B \equiv (\lnot A) \vee B \)
Contraposition	\( A \rightarrow B \equiv (\lnot B) \rightarrow (\lnot A) \)
Exclusive Middle	\( A \vee (\lnot A) \equiv T \)

Note

We did not have a chance during this lecture to cover all of these. We'll finish the table in the next lecture.

Using the table of basic equivalences to find new equivalences.

More practice using the table to compute logical equivalences.

More practice using the table to compute logical equivalences.

This entire lecture is a review session for the coming midterm exam. Students should bring questions!

Discussed some notions from elementary (combinatorial) probability.

• Events or outcomes
• Computing basic probabilities via counting outcomes
• Ambiguity and the importance of clear statement
• How students in the class understand probability
• Probability in our day-to-day life
• The distinction between statistics and probabilities

Suppose every (desired) outcome can be constructed by a sequence of \( k \) choices with…

• \( n_1 \) options for the \( 1^{\textrm{st}} \) choice,
• \( n_2 \) options for the \( 2^{\textrm{nd}} \) choice,
• \( \vdots \)
• \( n_k \) options for the \( k^{\textrm{th}} \) choice.

Then the total number of outcomes is \( n_1 \cdot n_2 \cdot \dots \cdot n_k \), PROVIDED

Independent

Numbers of options do not depend on actual choices made.

Unique

Each sequence of choices results in a different outcome.

We did many examples in class.

Suppose every (desired) outcome can be classified into \( k \) cases with…

• \( n_1 \) outcomes in the \( 1^{\textrm{st}} \) case,
• \( n_2 \) outcomes in the \( 2^{\textrm{nd}} \) case,
• \( \vdots \)
• \( n_k \) outcomes in the \( k^{\textrm{th}} \) case.

Then the total number of outcomes is \( n_1 + n_2 + \dots + n_k \), PROVIDED

Disjoint

No outcome belongs to two cases at the same time.

We did many examples in class.

We did several counting examples building a diagram of possible choices and then labelling the diagram with the number of options in each case. This effectively combines the product principle and the addition principle. For the sake of giving it a name, we'll call this the "tree method".

Our diagram has a "root" (i.e., the default state where no choices are made), and "branches" (i.e., the possible choices at each stage of the decision-making process). Then, we label the branches with the numbers of options on that branch. Finally, we use the product principle to obtain the full count on each "leaf" (i.e., each final state) of the tree by multiplying along branches followed from the root.

Discussed the distinction between ordered and unordered counting.

• \( C(k, n) \) is the number of ways to select \( k \) distinct objects from \( n \) distinct objects.
• Solved marble-selection problems (both ordered and unordered).
• Solved some counting problems dealing (tee-hee) with poker.
• Counted anagrams of words.
  • A word is any sequence of characters. An anagram of a word is any rearrangement of the same characters.

Count poker hands and compute their probabilities if cards are dealt at random.

More counting poker hands and compute their probabilities if cards are dealt at random.

We covered the following.

• Anatomy of the sudoku grid (rows, columns, boxes).
• Rules of the puzzle.
• Some basic solving techniques.
  • Hidden and naked singles.
  • Hidden and naked pairs/triples/quads/etc.

• Solved an example puzzle to illustrate the techniques. In fact, we discovered the techniques together as we needed them!

   . . . | . . . | . . .
   . 5 . | 7 8 . | 9 . .
   6 . 4 | 1 . . | . . .
  -------+-------+-------
   4 . . | . 6 . | . . .
   . . 8 | 5 . 7 | . . 1
   1 . . | 4 . . | . . 3
  -------+-------+-------
   . . . | 6 . . | . . .
   5 4 7 | . . . | . . .
   . 1 . | 9 3 . | 4 . 8
  

I gave students another puzzle for practice.

We went over another simple puzzle. We also discussed the X-wing technique.

Worked through a harder puzzle, including a few applications of the X-wing. Discussed the Swordfish technique.

We worked through a colouring of the recent puzzle Chromatic Windmill by Eric Rathbun. The remainder of the puzzle (not done in class) is a relatively straightforward exercise in analysing possible cases. You can see another person's approach to solving the puzzle in this YouTube video.

• No winning strategy! The optimal strategy can only guarantee a tie for first player!
• Counted (naively) approximations for the total number of Tic-Tac-Toe games.
• See this relevent xkcd comic for a complete map of the optimal moves and responses laid out in a tree-ish way.

You can get a grid for Fractal Tic-Tac-Toe from this website. The rules are described below (or you can get a printable copy, including examples).

Setup

Draw a large \( 3 \times 3 \) grid, and draw a smaller \( 3 \times 3 \) grid in each of it's squares.

Goal

Make a line of three of your symbol in the big grid.

Play

Two players (X and O) alternate placing their symbol in a cell of a small grid. Capture a big cell by winning the smaller game in that cell. When a player places their symbol in a cell, the next player must place their symbol in the corresponding grid in their next turn UNLESS…

• they are the first player (they choose where to play first), or
• their move would be on a grid already won or tied (they choose where to play next).

• Discussed the rules of the game Go.
  • Basic rules of the game.
  • More advanced rule discussion.
  • Brief recap of the rules with an interesting claim at the end (the video is a bit old).
• Watched parts of this documentary on AlphaGo, the Go-playing algorithm. The full documentary is quite interesting, and worth a look.
• Briefly discussed some of the dangers of blindly over-trusting AI. See this segment from Last Week Tonight for more information. Note: This is a partially humorous take, but the dangers discussed there are real, and the segment is well-done overall.

Students should bring questions. The final is cumulative, with an emphasis on things after the midterm.

During this lecture period, I laid out what kind of questions I will ask about each topic. None of what happens on the final should be a surprise if you attended today.

Our Final Exam is scheduled for Monday, 8 May 2023 at 09:00 in Woods Lab 121, because this section meets during Canonical Hour J.

Our Final Exam is scheduled for Sunday, 7 May 2023 at 19:00 in Woods Lab 121, because this section meets during Canonical Hour L.