Skip to content

And and Or ​

After finishing this section, you will be able to prove propositions involving "and" (∧) and "or" (∨). There is only one rule: whether it appears in the goal or in a hypothesis, the approach differs.

In the goal (you need to prove it)In a hypothesis (you have it in hand)
p ∧ qconstructor: prove p and q separatelyh.left, h.right: take out one half
p ∨ qleft or right: pick one side to provercases h with hp | hq: both cases must be discussed

How to type the symbols: in VS Code or the online version, type \and to get ∧, \or to get ∨, and \to to get →.

What you'll be able to do after this section ​

  • Prove an "and": prove both sides
  • Use an "and": take out the half you need
  • Prove an "or": pick the correct side
  • Use an "or": split into cases

Step 1: And ​

To prove p ∧ q, you must prove both p and q. constructor splits one goal into two:

lean
example (p q : Prop) (hp : p) (hq : q) : p ∧ q := by
  constructor
  · exact hp
  · exact hq

The · at the start of a line means "now focus on proving this one small goal". Type \. to get it.

Conversely, when you have h : p ∧ q in hand, h.left is a proof of p, and h.right is a proof of q:

lean
example (p q : Prop) (h : p ∧ q) : q := by
  exact h.right

On the course entry page, you proved "it is windy and rainy" in plain language. Now prove it as a theorem that holds for any p and q — walk through it yourself:

Prove it yourselfSwap the two sides of the "and"Status and errors are handled by Lean 4.35.0 Generate
theorem and_swap' (p q : Prop) : p ∧ q → q ∧ p := by
  intro h
  constructor
  exact h.right
  exact h.left

Write it as code:

lean
theorem and_swap' (p q : Prop) : p ∧ q → q ∧ p := by
  intro h
  constructor
  · exact h.right
  · exact h.left
  • I know that for an "and" in the goal I use constructor, and for an "and" in a hypothesis I use .left and .right

Step 2: Or ​

To prove p ∨ q, proving one side is enough. Use left or right to indicate which side you pick:

lean
example (p q : Prop) (hp : p) : p ∨ q := by
  left
  exact hp

Picking the wrong side means you can't finish the proof. You only have p in hand, but you picked the right side:

lean
example (p q : Prop) (hp : p) : p ∨ q := by
  right
  exact hp
text
Type mismatch
hp
has type
p
but is expected to have type
q

When you have h : p ∨ q in hand, the situation is different: you don't know which side holds, so you must handle both cases. rcases h with hp | hq splits the proof into two branches, one with hp : p, the other with hq : q.

  • I know that for an "or" in the goal I pick one side, and for an "or" in a hypothesis I must discuss both sides

Hands-on: swap the two sides of an "or" ​

Given "p or q", prove "q or p". Notice that after splitting into cases, the two branches pick exactly opposite sides.

Prove it yourselfSwap the two sides of the "or"Status and errors are handled by Lean 4.35.0 Generate
theorem or_swap' (p q : Prop) : p ∨ q → q ∨ p := by
  intro h
  rcases h with hp | hq
  right
  exact hp
  left
  exact hq

Write it as code:

lean
theorem or_swap' (p q : Prop) : p ∨ q → q ∨ p := by
  intro h
  rcases h with hp | hq
  · right
    exact hp
  · left
    exact hq

Quiz timeYou have h : p ∧ q, and the goal is p ∨ q. Which of the following works?

Checkpoint ​

  • I can write out from memory the two-row, two-column table at the top of this page
  • I finished the proof of or_swap' in the exercise
  • I know that · is used to focus on one small goal
  • I can type ∧, ∨, →

Didn't work? ​

After constructor there are two goals and I don't know which one I'm proving. Look at the topmost one in the goal state; case left or case right indicates which half it is. Use · to work through them one at a time.

The rcases line reports a syntax error. The vertical bar in the middle is the | key on the keyboard, and the names on either side are up to you.

Next section ​

Up to here, every step has been derived by your own hand. Next section covers a few tactics that can do the work for you: rewriting, simplification, and automatic arithmetic.

gaodong.aiAboutPrivacyContact

Independent tutorials, not affiliated with any product mentioned. Product names and trademarks belong to their owners. Check official pages for prices and policies.