Questions tagged [logic]
For challenges pertaining to mathematical logic and boolean algebra.
38 questions
13
votes
15
answers
1k
views
Write a program for generating all functions from two sets
If A and B are two nonempty sets (so two lists that have no repetition, where order is not important), a set f is a function from set A to set B, if and only if
f is a subset of AxB
if x∊A then there ...
- 2,020
5
votes
2
answers
238
views
Identify Redundant Infix Condition
Say there are three multisets A, B, C. An infix condition has form
<ON|FACING|NEAR> <a multiset>
where
ON requires ...
- 32.9k
1
vote
1
answer
323
views
The Parable of the Dagger Prelude
Taken from lesswrong.com
Once upon a time, there was a court jester who dabbled in logic.
The jester presented the king with two boxes. Upon the first box was
inscribed:
"Either this box ...
- 268
7
votes
2
answers
349
views
Fitch Proof of \$(p\Longrightarrow q)\iff\lnot p\lor q\$ with least amount of steps
In the smallest amount of steps, prove
$$(p\Longrightarrow q)\iff\lnot p\lor q$$
We base the proof system on this website. The related functionalities are:
Assumption. Assume that some statement is ...
- 2,014
19
votes
23
answers
2k
views
Name that logic gate!
Given the truth table of a non-trivial symmetric 2-input logic gate, output its name. The 6 possible input/output pairs are:
...
- 2,082
8
votes
0
answers
496
views
Write a proof checker for first order logic
This originally came from Give the best Chaitin incompleteness bound, but I realized that there was a fragment of this problem which still potentially gives a good coding challenge.
First Order Logic ...
- 261
8
votes
0
answers
279
views
Give the best Chaitin incompleteness bound
This was originally a pure mathematics question, but I think I've got the best chance for an answer here.
The Challenge
For concreteness, consider Peano Arithmetic (PA). For some language L of your ...
- 261
2
votes
2
answers
397
views
Implement the Quine-McCluskey algorithm
The Quine-McCluskey algorithm merges disjunctors in a disjunction like
$$
\lnot x_0 \land \lnot x_1 \land \lnot x_2 \land \lnot x_3 \lor\\
x_0 \land \lnot x_1 \land x_2 \land \lnot x_3 \...
- 1,668
16
votes
26
answers
2k
views
Implement the Conjunction of a Three-Valued Logic
Your task, should you choose to accept it, is to take two input values \$a\$ and \$b\$,
where \$a\$ and \$b\$ are in the set \$\{T, U, F\}\$, and compute and output their logical conjunction in a ...
- 1,693
14
votes
5
answers
845
views
Is this propositional formula an instance of an axiom?
Please help me automate my discrete mathematics homework. Given a valid propositional formula, check if it is an instance of one of Łukasiewicz's axioms. Here's how it works.
A term can be defined ...
- 1,373
3
votes
3
answers
1k
views
Programming Less-Than, Greater-Than and Equal-To functions using Restricted Source [closed]
I'm currently working with a branchless language which does not have native Less-Than, Greater-Than or Equal-To functions. I do however have min, ...
- 7,619
26
votes
21
answers
6k
views
14
votes
8
answers
1k
views
Is a statement of propositional logic always true?
The challenge is to golf a program that checks if a statement of propositional calculus/logic is a logical tautology (i.e. it is true for all possible values of the variables).
Input
Input formulas ...
- 1,446
12
votes
2
answers
476
views
The one counting challenge to rule them all!
Background
Mathematicians are interested in all kinds of algebraic structures, e.g. groups, rings, boolean algebras. Generally, we have several operations (addition, multiplication, meet, join, etc.), ...
- 805
22
votes
1
answer
875
views
Write a program that checks the consistency of modern mathematics
Modern mathematics has been formalised using set theory by various systems of axioms. Zermelo Frankel set theory with the axiom of choice (ZFC) forms an intuitive set of axioms and is hence most ...
- 3,339