Questions tagged [logic]
Questions related to mathematical logic and its use in computer science
866
questions
1
vote
0answers
20 views
Incomplete definition of function- first order logic
Let $\Sigma=\{c,f^1,R_1^2,...,R_k^2\}$ where $c$ is constant, $f$ is one argument function, and $R_i$ are binary relations.
Let $\Sigma_2=\{c,g^2,R_1^1,...,R_k^1\}$ where $c$ is constant, $g$ is two ...
0
votes
1answer
33 views
Problem with formalism in first order logic
This is a general question in first order logic.
Assume I have alphabet $\Sigma$ that contains one-argument function (among other symbols).
I want a new alphabet, $\Sigma'$, which is the same as the ...
1
vote
0answers
40 views
equivalence of validity above different alphabet
Given the next alphabets: $\,\,\Sigma_1=\{R^2,P^1,=^2\}\,\,,\Sigma_2=\{c,f^1,=^2\}.$
Prove of Disprove: There's exists an algorithm, that given formula $A$ above $\Sigma_2$, builds formula $A'$ above ...
1
vote
0answers
20 views
Herbrand universe with infinite terms (for a lazy programing language)
I am working with a toy programming language for my thesis. It is lazy evaluating so I can have infinite terms (for example the "infinite natural number" ...
2
votes
1answer
29 views
Proving that there are more problems than solutions
I have doubts regarding a proof of the following theorem:
'Set of all problems' is larger than the 'set of all algorithms' (or set of all C programs).
Put rhetorically, the theorem says that there are ...
2
votes
1answer
27 views
What are the limits of Boolean Algebra?
Any decision problem algorithm can be represented as a boolean expression. The rules of boolean algebra (De Morgan's law, distributivity, etc.) can be used to manipulate and simplify that expression, ...
3
votes
1answer
30 views
Is an AND gate which is noisy 1/3 of the time on only one of its inputs universal?
Imagine you have a noise-free NOT gate, and an AND gate with the usual truth table
00 0
01 0
10 0 (*)
11 1
but such that the case (*) is wrong 1/3 of the time, ...
0
votes
1answer
27 views
What Is the Currently-Known Simplest NOR-node Directed Cyclic Graph That Produces Pi?
Any directed graph (including a directed cyclic graph or DCG) has a complexity measure. We know that NOR is a universal logic gate, in the sense that a DCG whose nodes are n-input NOR gates can ...
0
votes
0answers
40 views
What is meant by A determine BC in functional dependency. How the validity of this statement will be checked
We use notation A determines BC in a database for functional dependency. Same way we use equations in mathematics which shows dependency of variables. We have inference rules in logics, functions in ...
0
votes
0answers
15 views
Software for proving tautology with steps
I'm looking for a software which can prove a tautology using logical equivalences.
It should be able to show each step. So you can follow the chain of reasoning.
Here is an example:
\begin{align}
(p\...
1
vote
2answers
244 views
Weird “proof” recursion
Assume we have some statement called $\alpha$. We will define a new statement $P(\alpha):="(\alpha\text{ can be proved})\lor(\lnot\alpha \text{ can be proved})"$
I claim that $P(P(\alpha))$ is always ...
0
votes
1answer
30 views
Is a Turing Machine a Well-formed formula?
Today i wrote something about the bijection between turing machines and recursive functions. And i describe a Turing Machine as a Well-formed formula because it seems like a WFF to me.
But is it ...
1
vote
1answer
40 views
Proving intuitionistic tautologies in Agda
I am to use Agda to prove some intuitionistic tautologies. One of them is the so called Weak Peirce's Law
$$
((((A \rightarrow B) \rightarrow A) \rightarrow A) \rightarrow B) \rightarrow B
$$
I ...
1
vote
0answers
37 views
What is the connection between finite automata and logic (sequential calculus)?
Languages recognized by finite automata are exactly those definable
by sentences of the sequential calculus, and also exactly those
definable by rational expressions (also called regular expressions)
...
1
vote
1answer
34 views
a conjunctive normal form that is a tautology
Are there any examples of CNF formulas that are tautologies?
Such that every clause contains different variables so phrases like (a or not a) are rejected?
0
votes
0answers
30 views
Please help me fix / finish this Fitch proof, I am stuck
Using the Fitch application and only Intro and Elim rules (& REIT if necessary), prove that
$$\forall x \forall y (P(x) \implies Q(y)) \iff (\exists x P(x) \implies \forall y Q(y))$$
is a logical ...
1
vote
0answers
18 views
Analogue of disjunction and existence properties for a Turing-complete programming language?
Quoting from Wikipedia:
In mathematical logic, the disjunction and existence properties are
the "hallmarks" of constructive theories such as Heyting arithmetic
and constructive set theories ...
0
votes
0answers
17 views
Hoare Triple Logic
I'm having trouble understanding the logic behind Hoare Triples. The question asks for the missing value of the precondition {X}
...
-2
votes
1answer
22 views
Are single complements the same as seperate complements?
Is (A' + B') the same as (A + B)' ?
Note: The apostrophe ( ' ) represents the complement
3
votes
1answer
28 views
Complexity of pattern matching for modus ponens logical conclusions
Is a Turing machine with added the following contant-time operation equivalent (in the sense that polynomial time remains polynomial time and exponential time remains exponential time) to a (usual) ...
2
votes
1answer
16 views
Padding a 2SAT clause
In http://web.mit.edu/neboat/www/6.046-fa09/rec8.pdf, I see that they pad a 2SAT clause $(x\vee y)$ to make it a 3SAT clause by writing $(x\vee y\vee p) \wedge (x\vee y\vee \neg p)$. Why doesn't $(x\...
1
vote
1answer
25 views
What is the Number of Possible Nonequivalent Propositions with $P_1, P_2, P_3$ Using $\iff$ Operator?
A multiple choice question asks this:
Number of nonequivalent propositions that only consist of $P_1, P_2, P_3$ and use the $\iff$ logical operator is?$$A)7\text{ }B)8\text{ }C)1\text{ }D)16$$
I am ...
1
vote
1answer
19 views
Two “bubble” loops in pseudocode; would they return the same thing?
I am trying to create a new form of a bubble loop and want to see if they would return the same truth values during runtime. Could I get a second pair of eyes to confirm if this is the case?
Note: ...
0
votes
1answer
110 views
Checking validity of formulas in first-order logic
Given four formulas in first order logic. Which of the following formulas are not valid? (In logic a proposition is valid if it never evaluates to $\bot$.)
$(\exists x P(x)\to Q)\to (\forall x (P(x)\...
0
votes
0answers
47 views
Can anyone explain the pigeon-hole encoding method in proportional logic
Someone there who worked with cardinal contraindications within the framework of propositional logic? I have a problem understanding the pigeon-hole method. It is a method of satisfaction. I have been ...
0
votes
1answer
22 views
Doubt regarding the implications of a 2-SAT constraint
Consider an example 2-SAT instance with the constraint (x1 ∨ x2).
This CNF has these two implications:
¬x1→x2 and ¬x2→x1.
"They actually mean, if x1 is false then x2 must be true, and if ...
0
votes
0answers
17 views
Newbie 2s complement to binary circuits help
I'm creating a circuit with in3, in2, in1, and in0, and outputs F11-F0. The circuit has to take the input in 2s complement and output the number in binary with the sign. F11 represents the sign bit (...
1
vote
1answer
28 views
Formal Logic - Natural deduction: Problem with assumptions about exists-negation
I'm stuck on how to progress with this proof, despite I have tried, I cannot see the next move.
Given this proof without predicate:
So far what I've accomplished:
My idea is, as I can't see any ...
1
vote
0answers
12 views
Good exposition of tableau for first-order logic with equality?
I'm looking for a resource (online or printed) that explains in a self-contained way the classic tableau for first-order logic with equality. All I can find are expositions of tableaux for first-order ...
2
votes
1answer
99 views
Number of substrings possible with even characters
Consider a string 'ABBAA'
Possible substrings with even number of characters are $4$
'ABBA' : Count of 'A' is even and 'B' is even
'AA' : Count of 'A' is even and 'B' is even - ($0$)
Similarly 'BB' ...
5
votes
2answers
119 views
How do computers *really* work? (at the most basic level)
While learning about computers I will read about RAM and Storage and the CPU, and while these explain the architecture of a computer and how parts of a computer work together, I still don't understand ...
1
vote
1answer
18 views
Proving using a SAT solver that KB entails D
Suppose you're given this KB:
$$KB = (A, A ⇒ B, A ⇒ C, B ∧ C ⇒ D)$$
How would you show using a SAT solver that $KB \vDash D$?
0
votes
2answers
43 views
Oracle that can only definitively say if an instance is unsatisfiable
Assuming I have an Oracle that takes as input a strictly 3SAT Boolean instance and states whether the instance is satisfiable or not. If it says instance is unsatisfiable then the instance is ...
1
vote
1answer
40 views
Number of substrings with exactly k distinct characters
Given a string s and an int k, return an int representing the number of substrings (not unique) of s with exactly k distinct characters. If the given string doesn't have k distinct characters, return ...
1
vote
1answer
27 views
Showing that a bijection preserves homomorphism
I have the vocabulary $\tau = \{+, 0 \}$ and the structure $R = (\mathbb{R}, +^R, 0^R)$ where $+^R$ is a binary function symbol representing the normal addition of numbers and $0^R$ is the constant $0$...
-1
votes
2answers
189 views
Encoding the theorem on friends and strangers in predicate logic
In every group chat of six (distinct) people on Instagram, there is a group of three (distinct) people such that either:
everyone in the group are friends
everyone in the group are strangers (i.e not ...
3
votes
0answers
26 views
CTL and the modal mu-calculus
Is there any literature / results to which fragment of the modal mu-calculus the logic CTL corresponds? I know that in order to tranlsate the until operators of CTL, it suffices to use a single mu-...
0
votes
1answer
27 views
Converting into CNF
I am still a bit confused by how to convert into CNF even though I have the rules written down.
How do I convert the following sentence into CNF?
$(I \lor M) \Rightarrow H$
I know I need to get rid of ...
1
vote
0answers
30 views
Multiple parameter predicates and the Relational Model
I've got a very general question about the relational model and it's relationship to 1st order predicate calculus. It will probably seem very basic to most, I'm afraid, a consequence of me grappling ...
1
vote
2answers
38 views
Propositional Logic: Entailment
Given the sentences, S1, S2, if S1 |= S2 then all models that satisfy S1 also satisfy S2, how is the following statement correct?
A ∧ ¬A |= B
How can something and ...
0
votes
2answers
46 views
In propositional logic how is the negation equivalent?
I am unable to understand how the negation of a sentence into CNF actually makes sense, hopefully somebody can explain it to me in understandable terms!
Given the sentence: If the battery is charged (...
0
votes
0answers
41 views
A necessary condition for a relation to be in 2NF but not in 3NF is that some non-prime attribute must be determined by a non-prime attribute
I will state the complete question now, since it did not fit in the title.
Is the statement given below correct?
A necessary condition for a relation to be in 2NF but not in 3NF is that some non-...
2
votes
0answers
38 views
Is there a diagram of related logics?
Proving software is based on logics and there any many logics. AFAIK all of the logics can be shown as a tree diagram of how they are related; for example, a tree of how types of number are releated
...
4
votes
1answer
54 views
Proving equivalence of two substitutions by induction
I'm trying to prove the following reduction:
$$
t\{x:=u\}\{y:=v\} = t\{y:=v\}\{x:=u\{y:=v\}\}
$$
under the following assumptions:
$x \neq y$
$x$ is not a free variable of $v$ (in symbols, $x \...
3
votes
1answer
56 views
What's the average number of transistor switches needed to do an N-bit x N-bit multiply?
I want to know how switch-efficient a multiplier can be. If I need to do many $N$-bit by $N$-bit multiplies, and each bit is determined by flipping a coin, what's the average number of transistor ...
2
votes
1answer
38 views
Clarifying the definition of reduction with regards to NP-complete problems
In my logic class we started learning about the different complexity classes. In particular, we focused on the NP complexity class. A problem is in NP if it is solvable in polynomial time using a ...
2
votes
0answers
346 views
Prove that PRE-WORK-POST is Turing Complete
This is a homework question and I am trying to fully understand what I have to do and how to go about it. Therefore, I don't want full answers to the question.
The programming language PRE-WORK-POST ...
4
votes
0answers
40 views
Do FOL theorem provers accept axiom schemata?
Axiom schemata (such as ZFC) are, in a sense, infinite sets of axioms. Do the ATPs designed to work with FOL (such as Vampire) accept axiom schemata?
I looked in the Vampire "manual" briefly,...
-2
votes
1answer
64 views
Consider 4 positive integers a,b,c,d having exactly 10^11 bits (considering the leading zeroes) in the binary representations
Consider 4 positive integers a,b,c,d having exactly 10^11 bits (considering the leading zeroes) in the binary representations. Positions are numbered from 1 to 10^11. Every 3rd bit of a is equal to 1 ...
0
votes
0answers
23 views
Comparing Registers with 16-bits
I am given with this information:
"CMP OP1,OP2 will compare registers OP1 and OP2 if they are equal,
flag values will be ZF=1, CF=0,
if the first
operands value is greater flag values will be ZF=...
