Questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions would fit very nicely under this tag. Questions about other kind of logics should be tagged with [logic] instead.
2
votes
3answers
119 views
Exercise in propositional logic.
Which of the following arguments is valid?
A. If it rains, then the grass grows. The worms are not happy unless it rains. Therefore, If the worms are happy , then the grass grows.
B. If the wind ...
0
votes
2answers
53 views
Intro to proof questions please help!!
1- Give a negation for each of the following statements. Do not just use the phrase "it is
not the case that . . . ."
(a) The square root of two is rational and Pi(3.14) is transcendental.
(b) The ...
1
vote
1answer
22 views
Is there some sort of function transformation expressing $(X\implies Y)\Leftrightarrow (\neg X\lor Y)$?
Is there a functional interpretation if the replacement for for the material implication?:
$$(X\implies Y)\Leftrightarrow (\neg X\lor Y)$$
Given a function from type $X$ to type $Y$, viewed as a ...
1
vote
1answer
73 views
Transforming statements of a query language to propositional logic
I have a custom query language which expresses containment relations between variables. Containment in this context is simply an object (A) in programming language X (java/C#/python etc: a language ...
0
votes
1answer
74 views
Stuck on proving demorgans with quantifiers
What I'm trying to prove, using propositional and quantifier rules, is
$$\neg \exists{x} \; A(x) \iff \forall{x} \; \neg A(x).$$
So far, I've only started proving it left to the right, and I'm ...
0
votes
1answer
78 views
writing formulas that use propositions p and q
I am stuck on this question which tell me to Write all formulas of length at most 5 that use propositions p and q.
I'm not quite sure where to start.
Any help would be greatly appreciated
0
votes
1answer
70 views
Converting a Proposition to DNF using proof systems
I have been attempting to convent a prop to DNF using a group of common rules, i have applied them all but i think i should be able to get it smaller, This is what I've got so far. Thanks!
$$(p \wedge ...
-3
votes
1answer
50 views
How to prove that a set of connectives aren't adequate
I guess we have to prove it somehow by an induction as I saw a few examples online. But it just makes absolutely no sense to me... Can somebody explain it in human language? Thank you very much.
3
votes
0answers
39 views
Boolean combinatorics
Every finite Boolean algebra has a "middle layer", corresponding to the subsets of size $n/2$ (when looking at the algebra of subsets of $[n]$) or to a set of formulas including $p_i, \neg p_i, p_i ...
3
votes
0answers
276 views
Constructor And\Or-graph on function transition of the alternating automata
In a And\Or-graph induced by the transition function, each node of G corresponds to a state q belonging to set Q of the state of the Automaton, for q with $\delta(q,a)=q1*q2$, the node is a $*-node$ ...
2
votes
0answers
117 views
Showing a formula is a tautology
I'm currently enrolled in a introductory course on logic and until now everything has been going great. I'm having some trouble with applying monotonicity and the strengthening/weakening of ...
1
vote
0answers
46 views
Can any axiom of a first order mathematical theory be written as a definition?
I have seen different axiomatizations of PA. I some, equality is defined in others is an axiom. The same can be said of addition and multiplication. So it is not clear to me why and when axioms are ...
1
vote
0answers
53 views
Equivalence of two very specific propositional calculi
Let $H$ and $L$ be two propositional calculi. $H$ has as inference rule modus ponens only, and three axiom schemes:
P1: $A\rightarrow . B\rightarrow A$
P2: $(A\rightarrow . B\rightarrow ...
1
vote
0answers
27 views
Structural Induction: Base case leads to a contradiction
To make my question clear, I will start with some definitions and notation from the book I am studying:
Definition:
A function $\theta$ from the set of formulas into the set of formulas is a ...
1
vote
0answers
44 views
Inverse function in multi-valued logic through the Webb function
Let Webb function in multi-valued logic as $Webb(x, y) = W(x, y) = Inc(Max(x, y))$. There is a theorem about any function in any multi-valued logic can be represented through the Webb function.
Then ...
1
vote
0answers
164 views
proof of validity of tautology in first order logic
Every first-order logic formula which has a tautological shape in propositional logic is a valid formula. Will it be possible to give a formal proof for the above ? Thanks and Regards.
0
votes
0answers
18 views
First order logic - Proof: z is valid under structure S iff not z is not satisfiable
This is what I want to prove:
Prove that: formula $z$ is valid in $S$ if and only if $\lnot z$ is not satisfiable in $M = (D,I)$.
This is my attempt:
Consider $z$ valid in $M$. Consider ...
0
votes
0answers
36 views
a problem in understanding the proof of recursion theorem ?
there is some problem in understanding the proof of recursion theorem in the text , mathematical introduction to logic by enderton page 44 ,
we have a set U and a subset B of U and C is the subset ...
0
votes
0answers
29 views
Implementation Of Resolution Refutation In SML
I need to implement resolution refutation for predicate logic to verify if a set of clauses form a logical consequence of a given set of antecedent clauses. I need to code this in SML. Can someone ...
0
votes
0answers
170 views
maximal consistency of formula sets
I need to find example sets:
a) a set which doesn't have a maximal consistent extension
b) a set which has exactly one maximal consistent extension
b) a set which has exactly two maximal consistent ...
0
votes
0answers
158 views
propositional logic - substitution
Prove: $\varphi_1 =\!\mathrel|\mathrel|\!= \varphi_2 \implies \varphi_1[\psi/p] =\!\mathrel|\mathrel|\!= \varphi_2[\psi/p]$.
We've proven that $\varphi_1 =\!\mathrel|\mathrel|\!= \varphi_2 \implies ...
