|
Равносильны ли формулы ∀x∀y∀z(R(y,x)→R(z,y)) и ∀x∀yR(х,у)∨∀x∀y¬R(х,у) ? задан 14 Янв '18 14:07 
Jenya |
|
Да, равносильны. Проверим это. Пусть вторая из формул истинна в некоторой интерпретации. Покажем, что первая в ней тоже истинна. Имеет место один из двух случаев: любые элементы предметной области находятся в отношении R, либо никакие не находятся. В первом случае импликация R(y,x)->R(z,y) имеет вид 1->1. Во втором она же имеет вид 0->0. При этом она в обоих случаях оказывается истинной. Теперь проверим, что если первая из формул истинна в некоторой интерпретации, то и вторая тоже истинна. Допустим, что отношение R пусто. Тогда доказывать нечего: последний дизъюнктивный член второй формулы даёт истинность. Если же отношение непусто, то существуют элементы предметной области a,b такие, что R(a,b) истинно. Отсюда с учётом истинности первой формулы следует, что R(z,a) истинно при любом z. А из этого уже следует, что R(y,z) истинно при любом y и любом z. Тем самым, отношение R является полным, и даёт истинность первого дизъюнктивного члена второй формулы. отвечен 14 Янв '18 16:01 
falcao так, если мы вынесем кванторы во второй формуле, т е ∀x∀yR(х,у)∨∀x∀y¬R(х,у) ~ ∀x∀y¬R(х,у)∨∀x∀yR(х,у)~∀у∀х¬R(у,х)∨∀z∀yR(z,у)~∀x∀z(∀у¬R(у,х)∨∀yR(z,у)). и это не эквивалентно этому ∀x∀y∀z(¬R(у,x)∨R(z,у)). Поэтому ответ кажется нераавносильны
(14 Янв '18 16:23)
Jenya
Т е ∀у(¬R(y)∨R(y))не эквив ∀у¬R(y)∨ ∀уR(y)
(14 Янв '18 16:32)
Jenya
|