Questions tagged [logic]
For challenges pertaining to mathematical logic and boolean algebra.
33 questions
7
votes
0
answers
414
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 ...
- 241
7
votes
0
answers
223
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 ...
- 241
1
vote
2
answers
345
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,638
16
votes
26
answers
1k
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,653
14
votes
5
answers
745
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
878
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,541
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,428
12
votes
2
answers
393
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.), ...
- 735
20
votes
1
answer
791
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,311
25
votes
2
answers
766
views
Existential Golf
Math has a lot of symbols. Some might say too many symbols. So lets do some math with pictures.
Lets have a paper, which we will draw on. To start the paper is empty, we will say that is ...
- 100k
1
vote
0
answers
210
views
3-inverter with two NOT gates [closed]
Introduction
I recently came across an oral exam where the candidates were asked to find a logical circuit than can negate 3 inputs A,B,C using only two NOT gates.
...
- 111
42
votes
3
answers
2k
views
(A → B) → (¬B → ¬A)
Well I think it is about time we have another proof-golf question.
This time we are going to prove the well known logical truth
\$(A \rightarrow B) \rightarrow (\neg B \rightarrow \neg A)\$
To do ...
- 100k
18
votes
2
answers
2k
views
Gerrymandering with Logic Gates
The majority function is a boolean function which takes three boolean inputs and returns the most common. For instance if maj(x,y,z) is the majority function and <...
- 2,115
7
votes
3
answers
462
views
Generate random LTL Formulae [closed]
An LTL Formula l is defined by the following grammar (where <x> describes the non-terminal symbol x):
...
- 701
7
votes
4
answers
432
views
Quickly Prove Me Wrong!
Introduction
This is the evolution of this previous challenge which was about checking satisfieability of normal formulae in conjunctive normal form (CNF). However, this problem is NP-complete and ...
- 3,403
59
votes
75
answers
5k
views
Be the First 1 (leave only the first Truthy)
Intro
Every year, Dyalog Ltd. holds a student competition. The challenge there is to write good APL code. This is a language agnostic code-golf edition of this year's eighth problem.
I have explicit ...
- 31.1k
2
votes
0
answers
73
views
Skip or delete lines between two keywords in a file using python [closed]
The problem is I need to skip or delete all the lines between the two keywords in a file and the keyword pair will appear many times in the file.The file looks something like this
...
- 21
1
vote
0
answers
65
views
Cheeky bus driver [duplicate]
The bus driver picks up the children from their homes every morning for school. All the homes are positioned around a circular street and the bus driver has to stop at every home exactly once.
One ...
- 11
195
votes
64
answers
31k
views
Mathematics is fact. Programming is not
In mathematics an exclamation mark ! often means factorial and it comes after the argument.
In programming an exclamation mark ! ...
- 90k
36
votes
18
answers
5k
views
Automate your first grade counting exercise
CodeGolf Challenge
PWSSHHHH! You wake up in a cryogenics lab in the year 3000. Upon being escorted to the assignment office to receive your career chip, presumably that of a delivery boy, a probe ...
- 3,139
12
votes
3
answers
3k
views
Convert a logical expression to conjunctive normal form
Goal:
Write a complete program or function which takes a formula in propositional logic (henceforth referred to as a logical expression or expression) and outputs that formula in conjunctive normal ...
user61980
69
votes
62
answers
4k
views
Count trailing truths
Inspired by, and in memory of, my dear friend and colleague,
Dan Baronet, 1956 – 2016. R.I.P.
He found the shortest possible APL solution to this task:
Task
Given a Boolean list, count the number of ...
- 31.1k
22
votes
3
answers
997
views
Prove DeMorgan's laws
Using the the ten inferences of the Natural Deduction System prove DeMorgan's laws.
The Rules of Natural Deduction
Negation Introduction: {(P → Q), (P → ¬Q)} ⊢ ¬P
...
- 100k
25
votes
82
answers
7k
views
Invert a boolean array
A nice simple one
Input
Given a boolean array (Or an acceptable alternative), you can assume the array will never be more than 32 elements long.
...
- 2,501
8
votes
4
answers
538
views
How secure are my locks?
You have been assigned the task of installing new locks to the company's building. However, the locks you use are quite unusual: they require some combination of keys to open. Now, you want to figure ...
- 17.9k
17
votes
2
answers
398
views
Given a truth table, output a Stackylogic program that satisfies it
Stackylogic is a programming language I made up in a previous challenge: Run Stackylogic. Read that post for full details and examples, but here is how it works paraphrased:
Stackylogic takes ...
- 90k
46
votes
11
answers
2k
views
Run Stackylogic
Stackylogic is a logic-based programming language I made up that take in 0's and 1's for input and outputs a single ...
- 90k
23
votes
3
answers
3k
views
Prove me wrong!
Introduction
Your mission in life is simple: Prove people wrong on the internet!
To do this you usually carefully analyze their statements and point out the contradiction in them.
It's time to ...
- 3,403
8
votes
1
answer
363
views
Solving variants of the blue-eyes puzzle
The original "Blue Eyes" puzzle is given here (and below).
A group of people with assorted eye colors live on an island. They are
all perfect logicians -- if a conclusion can be logically deduced,...
- 3,311
3
votes
12
answers
1k
views
How's your string theory? [closed]
Back to the basics! You're in you comp sci class again, except wiser and golfier. You have the tools, you have the power… but do you have the skill? Probably.
Crash Course for the non-Computer ...
- 40.2k
50
votes
12
answers
5k
views
Alex is sometimes right
This challenge is to lift the spirits of our mod Alex A., who is usually wrong.
Suppose you have a friend named Alex who needs help with basic logic and math, specifically mathematical equivalence.
...
- 90k
46
votes
4
answers
7k
views
Are Pigs able to fly?
Task
Your task is to write a function or a program in a language of your choice that analyzes a couple of statements and determines whether it can be concluded from those statements that pigs are ...
- 849