brightoolhub. Français

Computer science · 03 / 06

Logic: test every possibility

High school · intermediate · Worked example and 4 exercises with solutions, at your pace.

Need a foundation?Binary: position determines weightAlgorithms: inputs, steps, output
UnderstandSee an exampleGuided exercise3 progressive challenges

The principle, simply

A boolean proposition is true or false. AND needs both true; inclusive OR needs at least one; XOR exactly one. Implication A ⇒ B is false only when A is true and B false. Truth tables compare expressions systematically.

THE PICTURE TO REMEMBERLogic: test every possibility
  1. 01Input possibilities
  2. 02Operator
  3. 03Row results
  4. 04Compare expressions

WORKED EXAMPLE

From principle to reasoning

For inputs 00, 01, 10, 11, AND is true only for 11; OR is false only for 00.

Solve a problem in this subject

  1. Specify the contract

    Define inputs, types, outputs and forbidden cases. State whether a search algorithm requires sorted data.

  2. Trace a small example

    Tabulate variables, tested conditions and actions using a small hand-checkable example.

  3. Test boundaries

    Consider empty inputs, one item, duplicates, missing values and numeric limits where relevant. Define the output or explain rejection.

  4. Justify

    Explain termination and correctness. Distinguish operation counts, measured time and memory use.

YOUR TURN

01 · Try before checking

Do OR and XOR always agree?

One hint

Inspect two true inputs.

Reveal and understand the solution

No: with A = B = 1, OR is 1 but XOR is 0. One counterexample disproves equivalence.

Compare method, conditions and answer; identify the exact part to revisit.

IMPROVE THROUGH PRACTICE

Three additional challenges with solutions

Start with the first challenge. Write your method before opening a hint; use the solution to find the first step that needs work.

Reflect after practising
02 · Recognise and understandLink to this exercise

For A true and B false, find A AND B and A OR B.

A hint to get started

AND needs both true; inclusive OR needs at least one.

Step-by-step solution
  1. A AND B is false.
  2. A OR B is true.
  3. Inclusive OR also remains true when both are true.

Which step did you miss? Retry without help, then explain why the method works.

03 · Apply the methodLink to this exercise

Compare NOT(A AND B) with NOT A OR NOT B.

A hint to get started

Test four combinations or use De Morgan.

Step-by-step solution
  1. The expressions are equivalent.
  2. When A and B are true, both are false.
  3. In the other three cases both are true.

Which step did you miss? Retry without help, then explain why the method works.

04 · Go furtherLink to this exercise

Is A ⇒ B equivalent to B ⇒ A? Give a counterexample.

A hint to get started

Try A false and B true.

Step-by-step solution
  1. With A false and B true, A ⇒ B is true in propositional logic.
  2. B ⇒ A is false.
  3. An implication is not equivalent to its converse.

Which step did you miss? Retry without help, then explain why the method works.

The trap to avoid

Inclusive OR differs from an exclusive either/or.

Without notes, can you…

  • Explain the principle in your own words?
  • Rebuild the diagram and its connections?
  • Solve the exercise and justify the method?

Choosing a state saves it in this browser. This is your assessment, not a grade.

Next chapter My notebook