-1
votes
2answers
26 views

One output for input of $n$-tuples using AND, OR, NOT

Let $B$ be set of $\{0,1\}$ and $B_n$ be the set of all strings of length $n$. How many functions can be constructed from $B_n$ to $B$ using logical operators like AND, OR, NOT. Help $\rightarrow$ ...
-2
votes
0answers
37 views

Pumping Lemma & Regular Language

For each regular language L, we have an integer k such that: ...
9
votes
2answers
173 views

The mother of all undecidable problems

It is usual to show that a problem P is undecidable by showing that the halting problem reduces to P. Is it the case that the halting problem is the mother of all undecidable problems in the sense ...
1
vote
2answers
92 views

Names of 3 input logic gates

I've tried to look this up online, I may have used the wrong terminology. This question is about the names of logic gates with three boolean inputs, and one boolean output. This is a truth table for ...
0
votes
0answers
44 views

predicate logic with assumption NP $\neq$ CO-NP?

Anyone could describe why: Set of All Tautology in propositional logic with assumption NP $\neq$ CO-NP is CO-NP Complete. Thanks. I ask it here before: Is the language of tautologies NP-complete? ...
0
votes
2answers
40 views

What is the Equivalent formula of $((a\to b) \to ((a \to c) \to (c \to a)))$

Need help to solving a logic. The question is to find an equivalent to the following logic. $((a\to b) \to ((a \to c) \to (c \to a)))$ Thanks in advance for help.
0
votes
1answer
27 views

Computable Function and Predicate Question

I See on Our Lecture note on Theory of Computation Course that: .... The basic characteristic of a computable function is that there must be a finite procedure (an algorithm) telling how to compute ...
2
votes
1answer
80 views

Many to one Reducible & Polynomial time

we know that If $A \le_p B$, then $A$ can be reduced to $B$ in polynomial time. we know that If $A \le_m B$, then $A$ is many to one reduction to $B$ . can we deduce that: if $A \le_m B$ then $A ...
-1
votes
1answer
48 views

prenex equivalence problem

Suppose: $$\forall x\exists y \phi(x,y) \to \neg \exists x\psi(x) $$ which of the following formula are prenex normal equivalence with the above formula? i didn't any idea to explain it. it's a ...
-1
votes
1answer
55 views

Computable Set & Function

we know that i read this sentence are true? can anyone say an example for following sentence? there are a non computable set A such that
0
votes
1answer
89 views

Turing & Computability & Computation

We know if we have: we can show (T=t= Turin Redu.) but i have no idea why this relation be correct? any idea?
0
votes
0answers
63 views

TAUTOLOGIES NP-Complete Condition

The decision problem TAUTOLOGIES is, Given $\forall x_1 \forall x_2 ... \forall x_n$ $\phi(x_1, x_2, ... x_n)$ a set of universally quantified Boolean variables and a Boolean formula ...
0
votes
1answer
56 views

Function Combination on Computer Science

I read some material on Computational Function, every one could describe the result of following combination? suppose $g_1(x)=3x$, $g_2(x)=4x$, $f(x,y)=x+y$, how we compute combination of $f$ with ...
0
votes
0answers
72 views

Primitive Recursive Predicate Challenge

I'm an Computer scientist, and I recently ran into a challenge. If we have primitive recursive predicate $P(x), Q(x)$, I think that all of following 4 expressions can be primitive recursive. Any hint ...
0
votes
0answers
46 views

Recursive Set and Complement Problem

if we have $$A=\{x:|W_x\ne\phi\}$$ can we say always my tight listed below is true? $A$ is recursive , $A$ is r.e, complement of $A$ is r.e, complement of $A$ is not recursive?
0
votes
1answer
52 views

Complexity & Computation & Logic Problem [closed]

As i study for prepare to CS Final exam, i have some challenges. can i say all of following statements are true? 1) each infinite recursive set, is union of two disjoint infinite recursive set? 2) ...
1
vote
1answer
53 views

Semantic consequence

I'm studying refutation trees in computer science II, but I have a big doubt: Let $\Gamma, \Psi \subseteq F_m$ Is the following hypothesis true? $\Gamma \vDash \Psi \iff \not\vDash\{\Gamma,\lnot ...
0
votes
2answers
36 views

Gives regular expressions which defines regular language and what does {1,2} mean

The question is give a regular expression which defines a regular language. Question: The language over {0,1} consisting of all strings which either have length less than 3 or have 0 as their third ...
1
vote
1answer
35 views

The approximation rule implies the equality rule in systems of type assignments

I'm reading Barendregt's Lambda calculi with types (1992). In Proposition 4.1.4.1., he "proves" a lemma which shows the approximation rule implies the equality rule in typed lambda-calculi à la ...
0
votes
0answers
36 views

Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality

The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...
0
votes
0answers
70 views

Boolean algebra - cube - minimal disjunctive normal form

I have a test coming up and I would like to know how to solve these kinds of problems. This is the description: ...
0
votes
1answer
66 views

Checking Boolean Algebra work - Simplification

I am currently working on an assignment for a CE class I am taking, and I wanted to know if I have been simplifying these equations correctly. I'm supposed to reduce them to a sum of products. 1) ...
4
votes
1answer
43 views

Transforming Nested Fixed-Point Formulas into Infinitary Logic Formulas with Finitely many Variables

There is a definition (actually a description of how it could be defined) of a fixed-point logic formula. The formula is in inflationary fixed point logic (IFP) in this case but it could also be ...
0
votes
3answers
40 views

Reference for problems without efficient algorithm (in polynomial time)

I'm writing paper and need your help in finding some famous (or not so famous) problems without efficient algorithm, but from logic or computer science. So far, I have: -Boolean satisfiability ...
1
vote
1answer
46 views

Logic question- its about propositional logic and it asks for a valuation for statisfiability

I dont understand this question that comes from a past paper, so please any help is appreciated. The part that i dont understand is what does it mean (question 3) that it wants me to consider the ...
10
votes
1answer
171 views

Is it possible that P != NP cannot be proved?

I am probably asking a stupid question but what I gather from a layman explanation of Godel's incompleteness theorem is that it is completely possible that a true statement cannot be derived from ...
0
votes
1answer
30 views

first order definability with $<$ vs $Succ, 0$.

In first order logic formulae with just the predicate $<$ could describe more structures than first order formulaes with $Succ$ (successor predicate) and a constant $0$ such that $\forall x (\neg ...
1
vote
0answers
66 views

Cut-off Subtraction in Coq

I am new to the world of computer assistant proof programs in general, and Coq in particular. As a result, I have sought to prove some elementary results about integers as a way to … At the moment, I ...
2
votes
1answer
168 views

lambda calculus and category theory

I am not particularly knowledgeable in either lambda calculus or category theory, but I am starting to learn Haskell so I would like to ask: are there connections between category theory and lambda ...
1
vote
2answers
147 views

$\beta$ - conversion and $\alpha$-reduction problem in $\lambda$-calculus

Here is an expression that I am trying to reduce and my operations so far: $$((\lambda x.(x (\lambda z.zy))) (\lambda z.\lambda y. zy) )= (x (\lambda z.zy))[x \to \lambda z.\lambda y. zy ] = ...
0
votes
1answer
56 views

Is this $\beta$-reduction well defined?

Would it be possible to apply $(\lambda x.\lambda y. x)$ to the argument $y$? It seems to me that this must not be possible as it would give a different answer if applied to a constant, call it ...
0
votes
1answer
149 views

Propositional Logic - induction

(a) Let C be the set {∧,∨} of propositional connectives, and let P be any set of propositional variables. i. Suppose that: φ is a well-formed formula that uses only connectives in C and variables ...
3
votes
1answer
46 views

A diophantine program for a basic For Loop

By Matiyasevich, every computable function has a diophantine representation. I am wondering if there is a general way to represent a simple iterative for loop. Specifically: Let $f(x)$ be any ...
2
votes
2answers
93 views

Boolean Algebra-Simplification Assistance Needed

I have to show that (!(P.Q) + R)(!Q + P.!R) => !Q by simplifying it using De Morgan's Laws. Here is what I did but I'm not sure it's right. (!(P.Q) + R)(!Q + P.!R) => !Q (!P + !Q + R)(!Q + P.!R) ...
1
vote
1answer
125 views

How to perform divide step of in-place Quicksort?

I have an example of quicksort, it says like this: The divide step of in-place quicksort works by showing how the following list would look after performing the division with the first element as ...
1
vote
0answers
50 views

A diophantine definition of the Kleene star

Let $f(x \, | \, y_1, \dots, y_n)$ be a Diophantine polynomial that generates the Diophantine set $F$. By Matiyasevich, the set $F^*$ (Kleene star of $F$) is also Diophantine. My question: how can ...
1
vote
1answer
67 views

Modal logics and logics with integer or even rational numbers - is that possible?

I am trying to find some research trends (publications, keywords for futher search, etc.) on logics and modal logics whose predicates can containt integer or even rational numbers (like x>2, x^2>3, ...
4
votes
1answer
192 views

Are there dual logic gates?

In category theory the usefulness of dualising such devices as monoids to comonoids has been shown, where multiplication which takes two inputs to one output is dualised to comultiplication which ...
2
votes
1answer
88 views

Describe a graph through logic

At the moment I'm in need to learn how to describe a graph through a logic statement such as: $$ \forall x\forall y(r(x,y) \to \lnot s(y,x) \land \lnot s(y,x)) \land \exists (s(z,z) \land \lnot ...
4
votes
1answer
73 views

Any work on Automated theorem proving by Pattern Recognition?

Are there some mathematicians or papers about Advanced ATP by Pattern recognition? Pattern recognition: recognize the patter from mathematic sentence, proof sequence.
9
votes
0answers
167 views

Reference on standard types

This question is about what I presume is a basic construction in type theory. The finite types are defined as follows: 0 is a finite type; if $\sigma, \tau$ are finite types, then so is ...
0
votes
1answer
209 views

Godel number and expressibility [duplicate]

how to show that these properties of strings of symbols are expressible: 1) being a term, 2) being a formula 3) being a sentence 4) being a proof in PA and where a property (i.e., predicate) P of ...
10
votes
3answers
265 views

What is necessary to exchange messages between aliens? [closed]

Lets assume that two extreme intelligent species in the universe can exchange morse code messages for the first time. A can send messages to B and B to A, both have unlimited time, but they can not ...
1
vote
1answer
182 views

Expressibility and numbering

A predicate $P$ is expressible (in PA) if there exists a formula $\phi(x_1,\ldots, x_n)$ of $L_A$ such that for all $m_1,\ldots, m_n$ elements of $\mathbb{N}$, we have that $P(m_1,\ldots, m_n)$ holds ...
1
vote
1answer
173 views

Second incompleteness and Model theorey

If we let $T$ be a consistent theory in the language of arithmetic $\mathcal{L}_A$ theory extending Peano Arithmetic — with specified numbering of formulas $\left[\cdot\right]$ and suppose that ...
2
votes
2answers
307 views

Are axioms and rules of inference interchangeable?

There is an equivalence between cellular automata and formal systems, you can code one into the other and vice versa. But in the the cellular automata (CA) the rules of inference are fixed and are ...
0
votes
1answer
211 views

Proving By reduction from the Halting Problem

I want to solve the following exercise in Computability and Complexity Theory: By providing a reduction from the HALTING problem to REACHABLE-CODE, prove that REACHABLE-CODE is undecidable. ...
2
votes
3answers
210 views

Beyond Goedel incompleteness and lack of soundness/completeness of higher-order logics

As I understand that there are at least two fundamental limits of the development of the mathematics: 1) Goedel incompeleteness theorems (or more clearly Church thesis) effectively says that there ...
2
votes
2answers
32 views

Get A⊕(B+1) from A⊕B

I have numbers A,B,C.D. (⊕ is XOR) C = A⊕B D = A⊕(B+1) Is there any way to get D from C, when I do not know A and B? How? Thanks for help!
4
votes
1answer
90 views

Which categories correspond to the untyped and typed lambda calculus?

Simply typed lambda calculus is the internal language of Cartesian Closed Categories. What category has its internal language the typed lambda calculus? And the untyped lambda calculus? Can we in ...