Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [logical-validity]

The tag has no usage guidance.

0
votes
0answers
31 views

Calculus methods and computability

We know about calculability of a function or computability. We looks for the ability to solve a specific problem / compute a function with calculus method. But if we define a calculus method, is ...
5
votes
2answers
173 views

Undecidable predicate logic is decidable by people?

Logic in computer science (By Michael Huth,Mark Ryan, second edition, page 132) says Every φ can, in principle, be discovered to be valid or not, if you are prepared to work arbitrarily hard at ...
0
votes
0answers
28 views

Show the Invalidity of the sequence

∃x (P(x) → Q(x)), ∃x P(x) ⊨ ∃x Q(x) I am trying to find the invalidity of the following sequents. A = Set of natural number P(x) : x is odd Q(x) : x is not divisible by 2 What i don't understand ...
1
vote
1answer
37 views

Showing the following sequents are not valid

$\lnot \forall x P(x) \models \forall x \lnot P(x)$ $P(x) : x$ is divisible by 2 or $P(x) : x$ is a dog. or $P(x) can be anything. I want to show the following sequents are not valid ..Isn't the ...
1
vote
1answer
43 views

Verifying execution of code in trustless environment

Let us assume I have a Program P running on remote computer generating output O. Without trusting the remote environment and not having to verify the output O, is there is a way to validate that ...
3
votes
1answer
96 views

Contingent sentences can always be true

I have a question about contingent sentences. To my knowledge, contingent sentences are sentences that are neither tautologies nor contradictions. In a textbook I read that a sentence might always be ...
-1
votes
1answer
74 views

Horn clause for the following formula

Let be $$F=A\land (\neg A\lor B)\land(A\lor \neg C)\land(\neg A\lor\neg B\lor D)\land(\neg A\lor\neg B\lor\neg C)$$ a formula. Is $F$ satisfiable? Well, firstly, I've put $F$ into another form: $$...
1
vote
0answers
137 views

Proving the following chain of implications

I'm struggling with a proof in the text for my logic course, and I'm wondering if someone could offer a hint or some help. The question is basically as follows. Show that if the decision problem for ...
0
votes
1answer
58 views

If $F$ is valid then $F \cup \{res(C_1,C_2,A_i)\}$ is valid

I have to prove the following problem in propositional logic: Let $F$ be a set of clauses and let $F' = F \cup \{res(C_1,C_2,A_i)\}$ be the extension of $F$ by a resolvent of some clauses $C_1,C_2 \...
1
vote
2answers
93 views

Using the rules of inferences

I know the rules of inferences and logical equivalence but I cannot seem to validate this argument. I rewrote the first premise as $\neg p\vee q$ other from that I am stuck. Any help will be ...
2
votes
1answer
335 views

definition of formula validity

I read in some sources that valid formulas are tautologies (valid under every evaluation). In the others, I read that these are formulas that have conclusions true when premises are true. Are these ...
5
votes
1answer
1k views

Validity of predicate logic formulas

The following predicate logic formula is invalid (i.e. not a tautology): $\Bigl[\forall x \,\exists y {\,.\,} P(x,y)\Bigr] \implies \Bigl[\exists y \, \forall x {\,.\,} P(x,y)\Bigr]$ Which of the ...
2
votes
3answers
222 views

Is switching quantifiers allowed in this instance?

In Logic In Computer Science (2nd Edition - Michael Huth and Mark Ryan), exercise 2.4.12.k is the following: For each of the formulas of predicate logic below, either find a model which does not ...